a shot of dev knowledge

Related tags

How to determine if a string contains all unique characters

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

RELATED COURSES
View all Courses
Related Courses
Related Courses
View all Courses

Keep Exploring