search
HomeBackend DevelopmentC++Check if all strings in an array can be made identical by swapping characters

Check if all strings in an array can be made identical by swapping characters

Sep 22, 2023 pm 11:45 PM
arrayswap charactersStrings are the same

Check if all strings in an array can be made identical by swapping characters

In this article, we will explore the problem of checking if all strings in an array are the same by swapping characters. We will first understand the problem statement and then study simple and efficient ways to solve the problem, along with their respective algorithms and time complexity. Finally, we will implement the solution in C.

Problem Statement

Given an array of strings, determine whether all strings can be made the same by swapping characters.

Naive method

The simplest way is to sort the characters of each string in the array and then compare each sorted string to the next sorted string. If all sorted strings are equal, it means that all strings can be made equal by swapping characters.

Algorithm (simple)

  • Sort the characters of each string in the array.

  • Compare each sorted string to the next sorted string.

  • Returns true if all sorted strings are equal; otherwise, returns false.

C code (plain)

Example

#include <iostream>
#include <vector>
#include <algorithm>

bool canBeMadeSame(std::vector<std::string> &strArray) {
   for (auto &str : strArray) {
      std::sort(str.begin(), str.end());
   }
   
   for (size_t i = 1; i < strArray.size(); i++) {
      if (strArray[i - 1] != strArray[i]) {
         return false;
      }
   }
   
   return true;
}

int main() {
   std::vector<std::string> strArray = {"abb", "bba", "bab"};
   
   if (canBeMadeSame(strArray)) {
      std::cout << "All strings can be made the same by interchanging characters." << std::endl;
   } else {
      std::cout << "All strings cannot be made the same by interchanging characters." << std::endl;
   }

   return 0;
}

Output

All strings can be made the same by interchanging characters.

Time complexity (naive): O(n * m * log(m)), where n is the number of strings in the array and m is the maximum length of the strings in the array.

Efficient method

What works is to count the frequency of each character in each string and store the count in a frequency array. Then, compare the frequency arrays of all strings. If they are equal, it means that all strings can be made the same by swapping characters.

Algorithm (efficient)

  • Initialize the frequency array vector for each string in the array.

  • Count the frequency of occurrence of each character in each string and store it in the corresponding frequency array.

  • Compare frequency arrays of all strings.

  • Returns true if all frequency arrays are equal; otherwise, returns false.

C code (efficient)

Example

#include <iostream>
#include <vector>
#include <algorithm>

bool canBeMadeSame(std::vector<std::string> &strArray) {
   std::vector<std::vector<int>> freqArrays(strArray.size(), std::vector<int>(26, 0));
   
   for (size_t i = 0; i < strArray.size(); i++) {
      for (char ch : strArray[i]) {
         freqArrays[i][ch - 'a']++;
      }
   }
   
   for (size_t i = 1; i < freqArrays.size(); i++) {
      if (freqArrays[i - 1] != freqArrays[i])
      return false;
   }
   
   return true;
}

int main() {
   std::vector<std::string> strArray = {"abb", "bba", "bab"};
   if (canBeMadeSame(strArray)) {
      std::cout << "All strings can be made the same by interchanging characters." << std::endl;
   } else {
      std::cout << "All strings cannot be made the same by interchanging characters." << std::endl;
   }
   
   return 0;
}

Output

All strings can be made the same by interchanging characters.

Time complexity (efficient) - O(n * m), where n is the number of strings in the array and m is the maximum length of the strings in the array.

in conclusion

In this article, we explored the problem of checking if all strings in an array are the same by swapping characters. We discuss simple yet efficient methods for solving this problem, along with their algorithmic and time complexity. This efficient method uses a frequency array to compare the number of occurrences of a character, resulting in a significant improvement in time complexity compared to the simpler method.

The above is the detailed content of Check if all strings in an array can be made identical by swapping characters. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
C# vs. C   Performance: Benchmarking and ConsiderationsC# vs. C Performance: Benchmarking and ConsiderationsApr 25, 2025 am 12:25 AM

The performance differences between C# and C are mainly reflected in execution speed and resource management: 1) C usually performs better in numerical calculations and string operations because it is closer to hardware and has no additional overhead such as garbage collection; 2) C# is more concise in multi-threaded programming, but its performance is slightly inferior to C; 3) Which language to choose should be determined based on project requirements and team technology stack.

C  : Is It Dying or Simply Evolving?C : Is It Dying or Simply Evolving?Apr 24, 2025 am 12:13 AM

C isnotdying;it'sevolving.1)C remainsrelevantduetoitsversatilityandefficiencyinperformance-criticalapplications.2)Thelanguageiscontinuouslyupdated,withC 20introducingfeatureslikemodulesandcoroutinestoimproveusabilityandperformance.3)Despitechallen

C   in the Modern World: Applications and IndustriesC in the Modern World: Applications and IndustriesApr 23, 2025 am 12:10 AM

C is widely used and important in the modern world. 1) In game development, C is widely used for its high performance and polymorphism, such as UnrealEngine and Unity. 2) In financial trading systems, C's low latency and high throughput make it the first choice, suitable for high-frequency trading and real-time data analysis.

C   XML Libraries: Comparing and Contrasting OptionsC XML Libraries: Comparing and Contrasting OptionsApr 22, 2025 am 12:05 AM

There are four commonly used XML libraries in C: TinyXML-2, PugiXML, Xerces-C, and RapidXML. 1.TinyXML-2 is suitable for environments with limited resources, lightweight but limited functions. 2. PugiXML is fast and supports XPath query, suitable for complex XML structures. 3.Xerces-C is powerful, supports DOM and SAX resolution, and is suitable for complex processing. 4. RapidXML focuses on performance and parses extremely fast, but does not support XPath queries.

C   and XML: Exploring the Relationship and SupportC and XML: Exploring the Relationship and SupportApr 21, 2025 am 12:02 AM

C interacts with XML through third-party libraries (such as TinyXML, Pugixml, Xerces-C). 1) Use the library to parse XML files and convert them into C-processable data structures. 2) When generating XML, convert the C data structure to XML format. 3) In practical applications, XML is often used for configuration files and data exchange to improve development efficiency.

C# vs. C  : Understanding the Key Differences and SimilaritiesC# vs. C : Understanding the Key Differences and SimilaritiesApr 20, 2025 am 12:03 AM

The main differences between C# and C are syntax, performance and application scenarios. 1) The C# syntax is more concise, supports garbage collection, and is suitable for .NET framework development. 2) C has higher performance and requires manual memory management, which is often used in system programming and game development.

C# vs. C  : History, Evolution, and Future ProspectsC# vs. C : History, Evolution, and Future ProspectsApr 19, 2025 am 12:07 AM

The history and evolution of C# and C are unique, and the future prospects are also different. 1.C was invented by BjarneStroustrup in 1983 to introduce object-oriented programming into the C language. Its evolution process includes multiple standardizations, such as C 11 introducing auto keywords and lambda expressions, C 20 introducing concepts and coroutines, and will focus on performance and system-level programming in the future. 2.C# was released by Microsoft in 2000. Combining the advantages of C and Java, its evolution focuses on simplicity and productivity. For example, C#2.0 introduced generics and C#5.0 introduced asynchronous programming, which will focus on developers' productivity and cloud computing in the future.

C# vs. C  : Learning Curves and Developer ExperienceC# vs. C : Learning Curves and Developer ExperienceApr 18, 2025 am 12:13 AM

There are significant differences in the learning curves of C# and C and developer experience. 1) The learning curve of C# is relatively flat and is suitable for rapid development and enterprise-level applications. 2) The learning curve of C is steep and is suitable for high-performance and low-level control scenarios.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.