Check if a string has all unique characters

Question

This is a question from the book "Cracking the Coding Interview".

Implement an algorithm to determine if a string has all unique characters What if you can not use additional data structures?

I can use std::map but in interview they check logic. Suggest me some improvement for optimization.

#include <iostream>
#include <string>

class Strings
{
   static const int SIZE = 26;
   char alphabetL[SIZE] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
                            'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
                            'U', 'V', 'W', 'X', 'Y', 'Z'};

   char alphabetS[SIZE] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
                            'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                            'u', 'v', 'w', 'x', 'y', 'z'};

  public:
    Strings()  = default;
    ~Strings() = default;

    bool isAllUnique(std::string&);

  private:
    std::string toLower(std::string&);
};

std::string Strings::toLower(std::string& str)
{
    for (int i = 0; i < str.length(); i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            if (str[i] == alphabetL[j])
            {
                str[i] = alphabetS[j];
            }
        }
    }
    return str;
}

bool Strings::isAllUnique(std::string& str)
{
    int count[SIZE];
    for (int k = 0; k < SIZE; k++)
    {
        count[k] = 0;
    }
    str = toLower(str);
    for (int i = 0; i < str.length(); i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            if (str[i] == alphabetS[j])
            {
                count[j] = count[j] + 1;
                if (count[j] > 1)
                {
                    return false;
                }
                break;
            }
        }
    }
    return true;
}

int main()
{
    Strings obj;
    std::string str;
    std::cout << "Enter String\n";
    std::getline(std::cin, str);
    bool res = obj.isAllUnique(str);
    if (res == true)
    {
        std::cout << "There are unique characters in string\n";
    }
    else
    {
        std::cout << "There are no unique characters in string\n";
    }
}

Answer 1

People are very eager to present their own solutions, so let me attempt an actual review of your code:

• Your names could be clearer. Strings is not very descriptive, and neither are alphabetS/L. SIZE doesn't tell anyone what kind of size it is or what it relates to.

• Anything not nested under private or public in a class is automatically private. So you might as well move those stray members into the private section to make things clearer.

• If you're using C++11 or higher then you can use constexpr.

• Why are you returning a value from your toLower function after you pass in a mutable reference? Might as well drop the return and use the reference.

• Your toLower function does a lot of work. Assuming you don't want to use the STL for this you can still roll your own function. If you only want to check characters from A-z then you can simply get the lowercase by adding the difference to any number representation smaller than 97 (a). Look at the ASCII chart for reference.

• You can simply initialize count with int count[SIZE]{};. Alternatively you could use memset.

• Try to avoid performing more than one task in a function. E.g. factor out the toLower functionality of isAllUnique. It could then be const as it has no need to mutate class state.

• For the actual algorithm I prefer Incomputable's approach over the one suggested by Ben Steffan which can be used without overly relying on the STL.

• Prefer prefix over postfix for the increment operator.

• Don't compare to true. Instead simply do if (a_bool_var), or if (!a_bool_var) for the negation.

• This could probably be done with just free functions without needing a class object.

Answer 2

I believe the best approach here is to just use an array of 256 integers, which correspond to a counter to the numeric value of a letter.

std::array<bool, std::numeric_limits<unsigned char>::max()> seen = {}; //initialize to 0
for (char letter: str) {
    if (seen[letter]) {
        return false;
    }
    seen[letter] = true;
}

return true;

That way, algorithm will have constant space, and in general, be easy to understand and implement. If lowercase and uppercase letters are considered same, just take sum of the two.

Do note that the code requires adjustment to correctly handle signedness of char.

Answer 3

While you could approach this problem via a marking algorithm, the simplest way to achieve what you are trying to do is to sort the string and check for adjacent elements of the same type. Luckily, the standard library makes this very easy:

void to_lower(std::string& s) noexcept {
    std::transform(s.begin(), s.end(), s.begin(), [] (unsigned char c) {
        return std::tolower(c);
    });
}

auto has_no_duplicates(std::string& s) noexcept -> bool {

    if (s.size() > static_cast<std::size_t>(
        std::numeric_limits<unsigned char>::max()) + 1) {

        return false;
    }

    to_lower(s);
    std::sort(s.begin(), s.end());

    auto position = std::adjacent_find(s.begin(), s.end());
    return position == s.end();
}

This should be relatively straightforward: to_lower replaces every character in the string with its lowercase equivalent. has_no_duplicates first checks whether the string contains more characters than char can contain uniquely, which, by the pigeonhole principle, implies that there must be repititions. Next, it converts the string to lower case, sorts it, then uses std::adjacent_find to find the first position at which two equal elements appear next to each other. Since adjacent_find returns the end iterator in case that no such pair was found, the function just returns whether that is the case.

---

This solution has some drawbacks:

1. It assumes that the string to be checked is mutable. If this is not the case, the algorithm can be adopted to make a copy first, but that's pretty inefficient.
2. This is a multi-pass algorithm, whereas the problem could actually be solved in a single pass. Whether that matters or not depends on how important performance is.
3. Furthermore, this code has non-ideal time complexity: Whereas the problem can be solved by a marking algorithm in O(n), this algorithm runs in O(n log n) because of the sorting operation.
4. Once we're leaving fixed size encoded character sets, this method, as implemented here, won't work. One could say that this is more of a limitation of the string implementations C++ has to offer; however, this doesn't change the fact that this code is useless for, say, UTF-8 encoded strings.

Is also has some advantages compared to a marking algorithm:

1. It's very simple and very concise.
2. It doesn't consume much additional space. To be precise, the space complexity of this algorithm is O(1), as opposed to a marking algorithm which has complexity O(n) in the underlying character set size.

---

So, should you use this or not? Unless you are checking a lot of large strings, or your execution time hinges on this particular task being fast, I'd say that this solution is good enough.

If I were to interview a candidate and he presented me a solution like this, I'd be pretty happy. It's concise, it's pretty, and it shows that you know how to make effective use of the standard library.

(Take this last opinion with a grain of salt, though; I have no actual experience conducting job interviews, so this is only a personal feeling and not, in any way, based on experience or knowledge about what a recruiter might be looking for.)

---

Edit: As pointed out by Deduplicator, I was wrong about space complexity. I assumed that sort would run in constant space, whereas the standard doesn't guarantee this (however, it is possible that it does). I also added an additional fast-fail path as per hoffmale's suggestion.

Answer 4

Both the toLower and the isAllUnique functions miss a speed improvement that could be gained by using character math to compute array indexes, easily avoiding the nested loops:

• To convert upper case English letter to lower case of variable char c, you could do: if ('A' <= c && c <= 'Z') c = c - 'A' + 'a'

• To check that all characters are unique, you could use as storage bool seen[SIZE] = {false};, loop over the characters of the lowercased input, and if (seen[c - 'a']) return false; else seen[c - 'a'] = true;

This would be a lot shorter to write these functions, no need for the alphabet arrays, and perform much better. I would even do it in a single pass, performing the to-lower step character by character without the extra pass.

I find the dedicated class overkill. The code could fit nicely in a simple utility function.

---

What if you can not use additional data structures?

This question was not addressed. An easy answer is a nested loop, for each character checking if it doesn't appear in the rest of the string, with \$O(n^2)\$ time complexity. A simple optimization can be to make a first pass summing the values of c - 'a', and if it's not 0 + 1 + 2 + ... + 26 = 325 then return false immediately, otherwise fall back on the quadratic check.

Answer 5

I remember that particular question very well, because I got hung up on

What if you can not use additional data structures?

Well, what counts as a 'data structure'? For your charset 'A-Za-z' where case doesn't matter you could do something like

bool uniq(char str[], int i) {
    uint64_t uint_as_bitarray = 0;
    uint64_t char_as_flag;
    while (--i >= 0) {
        char_as_flag = (uint64_t) pow(2, tolower(str[i]) - 'a');
        if (uint_as_bitarray & char_as_flag) {
            return false;
        }
        uint_as_bitarray |= char_as_flag;
    }
    return true;
}

So, is uint_as_bitarray a data structure here? Implicitly maybe?

Charsets can be bigger, but so can integers. You can write the above in something like ruby and fit all of UTF-16:

$ ruby -e 'puts (2**2**16).class'
Integer

Answer 6

Although this question already has been answered I will add another answer at a higher abstraction layer.

Your Code

In short and blunt: I would not hire you with this code. The code is MUCH to complex and reeks of bugs (because of the complexity). Also you use a stateful class for a task that needs no persistent state over multiple invocations.

Please let me show you what I would expect from you and why.

Interviews

The point with interview questions is not only to find out wether you know the basics of a language. The main point of an interview is to find out if you would be good at the job.

So first, you will answer the question. Then the next question will very likely be, what are the advantages and disadvantages of your solution?

Answering the question: Loop

(sorry for syntax errors -- my last C was a long time ago)

The request to not [to] use additional data structures basically rules out all other answers here. A new array is still a data structure, albeit a very simple structure.

If you were to restrict yourself to primitives only you need to loop:

bool isOnlyUniqueValues(char[] test, int test_length) {
   // Test for each value in the test vector if a duplicate exists. 

   // i/k or „candidate_index/search_index for variable names is 
   // a matter of taste for such short algorithms
   for (int i=0; i < test_length; i++) {
     for (int k=i + 1; k < test_length; k++) {
       if (test[i] == test[k]) return false;
     }
   }
   return true;
}

This loop takes each character in the string and compares it to all the other characters in the string.

For example ("." is a placeholder for unique chars):

AA..   // <- The duplicate will be detected after one step (i=0, k=1)
0123


.A.A   // <- The duplicate will be detected after 3 + 2 = 5 steps (i=1, k=3)
0123

..AA // <- The duplicate will be detected after 3 + 2 = 5 steps (i=2, k=3)
0123

....   // <- Uniqueness will be detected after 3 + 2 + 1 = 6 steps (i=2, k=3)
0123

....... //  <- Uniqueness will be detected after 55 steps (i=8, k=9)
0123..9

What are the advantages and disadvantages of the solution?

This solution works well for small datasets (up to a few hundred chars in the string).

PRO:

• Easy to read
• For small datasets (a few hundred bytes) very cache efficient and probably the fastest solution
• No additional data structure

CON:

• Runtime of O(n^2), slows down with long (thousands of items) test vectors
• Worst case behaviour on unique items
• Fluctuating execution time (could be a problem in realtime or near realtime scenarios )

How would you improve the solution?

This is the interesting question! It shows if you find a solution to a problem or are just a "code monkey" that needs to be told every step of the solution.

First ask some questions (and these are always the same):

1. What is the (business) purpose of this function?
2. How large are the test data sets?
3. How frequent is it going to be executed?

There are other questions to be asked (Is this timing sensitive?, ...) but these three suffice here.

The (business) purpose and context

This will give you the context your code will under and which problem it should solve for the business. Remember: The best code is the code that does not need to be written! Maybe there are other solutions to the business problem.

This will you also give you an idea of your runtime context. Is this a server? Then RAM will probably much less of a problem than on an ATTiny.

Don't overdo this (esp. in an interview), but asking shows that you are capable of more than writing curly braces.

Size of the data set

This is a very important question. For small sizes you very likely will prefer easy to read code over overly complicated code. The larger the dataset, the more important the runtime complexity of your code:

1. Nested loops: O(n^2)
2. Set: O(n)
3. Filter (Bloom, Cuckoo, HyperLogLog ...)

In this case the size has the length of the alphabet (e.g. 255 for a string of bytes) as upper bound. Such a short alphabet case would make option #1 the best solution hands down.

Frequency of execution

If this code is called once per month then efficiency is probably not the main concern. If this code is in a timing sensitive code path (e.g. part of a web request) then performance is a must.

Other solutions

Here are the three solutions.

Plain nested loops

This is the solution presented. It meets all stated requirement (functionally: duplicates are found. No additional data structures or memory).

Set

A solution with a set works like the "map" solution from your example, although there is one difference:

A map basically maps Keys to Values (K -> V). A set is a unique set of values. Using a map really just exploits the fact that a maps keys form a set.

To rephrase the interview question: Is this string a set?.

bool isOnlyUniqueValues(char[] test, int test_length) {
   // I assume there is a std:set?
   std:set test_as_set = ...;

   for (int i=0; i < test_length; i++) {
     if (test_as_set.contains(test[i]){ return false;}
     test_as_set.put(test[i]);
   }
   return true;
}

PRO:

• Easy to read
• For small to largish datasets (a few thousand bytes) efficient
• Only simple additional data structure

CON:

• Memory overhead of O(n)
• Uses additional data structures

Filter

Filters are "approximate set membership data structures". The important word here is approximate.

The main differences versus the Set solution are

• Filters are extremely fast and only use small(ish) amounts of memory
• Filters can give you a false positive answer
• Filters a tuneable with respect to the "false positive" rate

The „might contain“ method of a filter can sometimes return true when the item is not in the set. If it returns false the value is guaranteed to be absent.

For details look at the Wikipedia page for Bloom Filter.

bool isOnlyUniqueValues(char[] test, int test_length) {
   // I assume there is a Filter implementation
   bloom_filter filter = ...; // here you also configure the error rate

   for (int i=0; i < test_length; i++) {
     // Closely look: The method is "might_contain"
     if (bloom_filter.might_contain(test[i]){ return false;}
     bloom_filter.put(test[i]);
   }
   return true;
}

PRO:

• Easy to read
• Efficient for extremely large datasets
• Good candidate for embedded systems (trade very small error rates for large performance and size improvements)

CON:

• Memory overhead
• Uses additional data structures
• Considered "advantaged" by most devs
• Overkill for most use cases
• Only gives probabilistic answers

Answer 7

The line count[j] = count[j] + 1; can be simplified. You shouldn't ever reach the state in which count[j] is anything other than 0 or 1. So you can simply do count[j] = 1. Or just use booleans.

For capital letters, you're iterating over the alphabet twice: first in toLower to find the lower case it corresponds to, and then in your main function to figure out what element of count[j] to change. You can get rid of toLower entirely and just do

for (int i = 0; i < str.length(); i++)
  {
    for (int j = 0; j < SIZE; j++)
    {
        if ((str[i] == alphabetS[j]) || (str[i] == alphabetL[j]))
        {
            if count[j]
            {
                return false;
            }
            count[j] = true;
            break;
        }
    }
  }
return true;

You could also get rid of the inner for-loop by casting str[i] as int.