How to Check if a Given String has Unique Characters?

Given a string s, determine whether it has all unique characters.

Example 1
Input
s = “abcde”
Output
true
Explanation
All characters only occur once

Example 2
Input
s = “aab”
Output
false
Explanation
There’s two as

Example 3
Input
s = “”
Output
true
Explanation
All characters occur once (of which there are none)

Topics: Hash Table

Check Unique String using C++ Hash Table

Using a hash table (set) requires O(N) space. Then we record the characters as they first appear in the string. If we meet a character that has already been in the string, we return false. Otherwise, when we iterate all the characters in the string, we know it is a unique string.

1
2
3
4
5
6
7
8

bool solve(string s) {
    unordered_set<char> seen;
    for (const auto &n: s) {
        if (seen.count(n)) return false;
        seen.insert(n);
    }
    return true;
}

bool solve(string s) {
    unordered_set<char> seen;
    for (const auto &n: s) {
        if (seen.count(n)) return false;
        seen.insert(n);
    }
    return true;
}

The time complexity is O(N).

C++ One Liner to check Unique String using Hash Set

Using a modern C++ syntax. We can actually check if a string is unqiue by creating a unordered set from the string and compare the size of the string and size of the set. If both are equal, it is unique.

1
2
3

bool solve(string s) {
    return unordered_set(begin(s), end(s)).size() == s.size();
}

bool solve(string s) {
    return unordered_set(begin(s), end(s)).size() == s.size();
}

The runtime complexity and space requirement is both O(N).

–EOF (The Ultimate Computing & Technology Blog) —