Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
communitycreator

How to determine if a string contains all unique characters

harris910

There are different strategies we can use to determine whether or not a string contains all unique characters. The typical approach uses brute force, but its complexity is O(n2)O(n^2), and we can certainly do better.

Algorithm (without an additional data structure)

  1. Sort the string based on the ASCII values of the characters (be careful, most of the sorting algorithm takes up extra space).

  2. Start the loop and then iterate through the characters of a string.

  3. Check the values of the characters that are next to each other.

  4. If the value does not match for all the pairs of characters in a string, then the string has all unique characters. Otherwise, it does not.

Initially
1 of 6

Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool uniqueCharactersInString(string strn)
{
    // sorts the string on the basis of ASCII values
    sort(strn.begin(), strn.end());
    //iterates and checks if two consecutive characters
    //are the same or not
    for (int i = 0; i < strn.length()-1; i++) {
        if (strn[i] == strn[i + 1]) {
            return false;
        }
    }
    return true;
}

int main(){
    cout<<"The string 'educative' has all unique characters: ";
    uniqueCharactersInString("educative")==1 ? cout<<"True":cout<<"False";
    cout<<endl;
    cout<<"The string 'code' has all unique characters: ";
    uniqueCharactersInString("code")==1 ? cout<<"True":cout<<"False";
}

Time complexity

The complexity of this function is O(nlogn)O(nlogn). The sorting algorithm we have used does in-place sorting and has a time complexity of O(nlogn)O(nlogn). Finally, the single loop takes O(n)O(n), so the overall complexity is O(nlogn)O(nlogn).

RELATED TAGS

c++
communitycreator
RELATED COURSES

View all Courses

Keep Exploring