Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
string
for loops

How to check if a string has unique characters using for loops

M. Squared

A string is a data type in C++ made up of characters that can be indexed and compared, like the elements of an array.

Example of a string indexed like an array

What is a unique string?

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.

Examples of unique and non-unique strings

Unique Non-unique
world hello
client server
square circle

Method 1: Using nested for loops

Logic and explanation

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 first iteration of the outer for loop, the character at index 0, 'w', will be compared with the remaining four string characters in the inner for loop. Similarly, in the second iteration, the character 'o' at index 1 will be compared with the remaining three string characters, and so on.

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 string
bool is_string_unique(string input)
{
	// initialize boolean variable as true
	bool is_unique = true ;

	for (int i = 0; i < input.length(); i++)
	{
		for (int j = i + 1; j < input.length(); j++)
		{
			// if a character is repeated
			if (input[i] == input[j])
			{
				// set boolean variable to false
				is_unique = false ;
				return is_unique ;
			}
		}
	}

	return is_unique ;
}

int main() 
{
  	string input ;
	cin >> input ;

	// function call 
	bool 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

Example code 1: Code using nested for loops

Method 2: Using single for loop

Logic and explanation

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.

The two instances of the non-unique character 'c' are placed next to each other after sorting.

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 string
bool is_sorted_string_unique(string sorted_input)
{
	// initialize boolean variable as true
	bool is_unique = true ;

	for (int i = 0; i < sorted_input.length(); i++)
	{
    // compare each character with its right neighbour
		if (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 function
	sort(input.begin(), input.end()) ;

	// function call 
	bool 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

Example code 2: Code using a sorted string and a single for loop

Conclusion

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(n2n^{2}). The second method, that involves the built-in sort() function, is relatively faster with a worst-case time complexity of O(nlognnlogn). However, a more efficient solution, in linear or constant time, can be obtained using additional data structures.

RELATED TAGS

c++
string
for loops
RELATED COURSES

View all Courses

Keep Exploring