A string is a data type in C++ made up of characters that can be indexed and compared, like the elements of an array.
A unique string consists of characters that occur only once. To check for uniqueness, compare each character with the rest of the string. If a character is repeated, then the string is not unique.
| Unique | Non-unique |
|---|---|
| world | hello |
| client | server |
| square | circle |
We can check for a unique string using nested for loops in C++. For each iteration of the outer for loop, the currently indexed string character is compared with all remaining string characters in the inner for loop. These for loops continue to traverse the string until a non-unique character is found.
In the following example code, the boolean function (is_string_unique()) takes the input string variable as an argument and checks for its uniqueness. The function returns false as soon as a non-unique character is found in the string. It returns true if the string is unique.
#include <iostream>using namespace std;// function to check uniqueness of a given stringbool is_string_unique(string input){// initialize boolean variable as truebool is_unique = true ;for (int i = 0; i < input.length(); i++){for (int j = i + 1; j < input.length(); j++){// if a character is repeatedif (input[i] == input[j]){// set boolean variable to falseis_unique = false ;return is_unique ;}}}return is_unique ;}int main(){string input ;cin >> input ;// function callbool is_unique = is_string_unique(input) ;if (is_unique){cout << "string is unique" << endl ;}else{cout << "string is not unique" << endl ;}return 0;}
Enter the input below
Alternatively, we can sort the given string first, and then check for its uniqueness. By sorting, we can place all non-unique characters next to each other in the string. This sorted string is then traversed using a single for loop. In each iteration, the currently indexed string character is compared with its neighbor. If a match is found, the loop is terminated.
In the following code, we have used the built-in sort() function provided in the C++ library to sort the input string. The is_sorted_string_unique() function takes the sorted_input string as its argument. It uses a single for loop to traverse the sorted string, while comparing each character with its right neighbor. The function returns false as soon as a match is found. Otherwise, if the string is unique, it returns true.
#include <iostream>#include <algorithm>using namespace std;// function to check uniqueness of a given stringbool is_sorted_string_unique(string sorted_input){// initialize boolean variable as truebool is_unique = true ;for (int i = 0; i < sorted_input.length(); i++){// compare each character with its right neighbourif (sorted_input[i] == sorted_input[i + 1]){is_unique = false ;return is_unique ;}}return is_unique ;}int main(){string input ;cin >> input ;// sorting input string using in-built sort functionsort(input.begin(), input.end()) ;// function callbool is_unique = is_sorted_string_unique(input) ;if (is_unique){cout << "string is unique" << endl ;}else{cout << "string is not unique" << endl ;}return 0;}
Enter the input below
It is important to note that the above solutions are simple yet inefficient. Although the space complexities of the above methods are considerably lesser than a solution that uses additional data structures, such as an array or a vector, the same cannot be said about their time complexities. The worst-case time complexity of the first method is O(). The second method, that involves the built-in sort() function, is relatively faster with a worst-case time complexity of O(). However, a more efficient solution, in linear or constant time, can be obtained using additional data structures.