Return to Revisions

Consider a simpler algorithm:

• Pass 1: Build a map of counts of characters. You can use a simple int array to store this mapping.
• Pass 2: For each index, if the count of the current character is 1, return the index.
• If pass 2 terminates without returning, then there are no unique characters, return -1.

This is simple, straightforward logic. The constant number of passes doesn't change the time complexity.

You could do it in a single pass too, but I would prefer to avoid the added complexity unless there is a compelling reason.

Example implementation of the above algorithm:

std::array<int, 26> counts {};

for (auto c : s) {
    counts[c - 'a']++;
}

for (std::size_t index = 0; index < s.size(); ++index) {
    auto c = static_cast<unsigned char>(s[index]);
    if (counts[c - 'a'] == 1) return index;
}

return -1;