Finding first unique character in string

Question

Below is a solution I came up with (in C++) for an algorithm that is supposed to find the first character in a string that only appears once in the input string (the input string is guaranteed to be made up of only lower case characters from English alphabet). The catch is that the algorithm must return the index of that character from the original string, or negative one (-1) if there is no such character.

The solution below is O(n) in time and O(1) in space (const space because the list and the map can never have more than 26 entries).

1. I'm not convinced that my use of data structures is precise/clean.
2. I'm not sure if the code is very readable as is. Would it be more effective to write small functions that say what they do to replace things like: map_char_to_tracking[s[i]].char_count_in_string == 1 [so the reader can read at a higher level of abstraction without having to know the details of the data structures]?

Any improvements would be much appreciated.

#include <iostream>
#include <list>
#include <unordered_map>

typedef struct
{
    int char_index_in_original_string;
    std::list<char>::iterator char_position_in_list_itr;
    int char_count_in_string;
}
    Tracking;

// O(n) time | O(1) space, where n is the number of characters in the input string.
int FirstOccurrenceOfUniqueChar(const std::string& s)
{
    std::list<char> unique_chars;
    std::unordered_map<char, Tracking> map_char_to_tracking;
    for (int i = 0; i < s.size(); ++i)
    {
        if (map_char_to_tracking[s[i]].char_count_in_string == 1)
        {
            // char has appeared once in string already, so remove it from unique chars list
            ++map_char_to_tracking[s[i]].char_count_in_string;
            unique_chars.erase(map_char_to_tracking[s[i]].char_position_in_list_itr);
        }
        else if (map_char_to_tracking[s[i]].char_count_in_string == 0)
        {
            // char hasn't appeared in string yet, so add it to unique chars list and map.
            unique_chars.push_back(s[i]);
            map_char_to_tracking[s[i]] = Tracking{ i, --unique_chars.end(), 1 };
        }
    }
    if (unique_chars.empty())
    {
        return -1;
    }
    return map_char_to_tracking[unique_chars.front()].char_index_in_original_string;
}
int main()
{
    std::string s1{ "abcdeabcd" };
    std::string s2{ "v" };
    std::string s3{ "" };
    std::string s4{ "aabbcc" };

    std::cout << FirstOccurrenceOfUniqueChar(s1) << std::endl; // expect 4
    std::cout << FirstOccurrenceOfUniqueChar(s2) << std::endl; // expect 0
    std::cout << FirstOccurrenceOfUniqueChar(s3) << std::endl; // expect -1
    std::cout << FirstOccurrenceOfUniqueChar(s4) << std::endl; // expect -1

    return 0;
}

Answer 1

As already mentioned, you can do this in a one-pass algorithm. You only need to keep track of whether you have seen a character before, and what the position of its first occurence is. Here is a possible implementation:

#include <algorithm>
#include <array>
#include <climits>
#include <cstdint>
#include <string>

std::size_t FirstOccurrenceOfUniqueChar(const std::string& s) {
    std::array<bool, 1 << CHAR_BIT> seen{};
    std::array<std::size_t, 1 << CHAR_BIT> pos;
    pos.fill(s.npos);

    for (std::size_t i = 0; i < s.size(); ++i) {
        auto ch = static_cast<unsigned char>(s[i]);
        pos[ch] = seen[ch] ? s.npos : i;
        seen[ch] = true;
    }

    return *std::min_element(pos.begin(), pos.end());
}

Note that in the above code, only two std::arrays are used; since there are only a fixed number of characters, you can use a fixed-size container instead of the slower std::list and std::unordered_map.

Also note that this version returns a std::size_t; this is necessary to support strings longer than an int can represent. Also, std::string::npos is used to indicate that there is no unique character. It's the largest possible value of std::size_t, which is very convenient here.

Also, if you cast std::string::npos to an int, it will become -1.

Answer 2

Consider a simpler algorithm:

• Pass 1: Build a map of counts of characters.
• 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;

Note that the hack of using c - 'a' to map lowercase English letters to the range [0 .. 25] works with the ASCII character set, and may not be suitable for others. If that's a concern, you can use the approach of the other answer, or use a proper std::set.

---

If there are more than INT_MAX repetitions of a character (as pointed out by @Toby), the count will overflow, and may even reach 1 again, producing incorrect result. If you need to add support for such input, then it will be better to consider a similar algorithm (alluded to by @greybeard):

• Pass 1: Build a set of characters seen, and another set of characters seen twice.
• Pass 2: For each index, if the character is not in the set of characters seen twice, return the index.
• If pass 2 terminates without returning, then there are no unique characters, return -1.

This uses an additional set (constant space), but has the advantage that it supports inputs of arbitrary length and repetitions.

Example implementation:

std::array<bool, 26> seen {}, repeated {};

for (auto c : s) {
    repeated[c - 'a'] = seen[c - 'a'];
    seen[c - 'a'] = true;
}

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

return -1;

Answer 3

We forgot to #include <string>.

---

This definition looks like C:

typedef struct
{
    ⋮
}
    Tracking;

In C++, we normally write

struct Tracking
{
    ⋮
};

I don't think there's anywhere we still need typedef in modern C++.

Since this type is used only within the function, it can be defined within that scope, making the global namespace a tiny bit tidier.

---

We use the wrong type for an index into a string. Strings can be longer than INT_MAX, so we should use std::size_t for char_index_in_original_string.

---

Although the contract of std::list says that its iterators remain valid when different elements are removed, it's hard to reason about this in the code, so I would avoid storing iterators if at all possible.

---

When we first see a particular character, a Tracking is default-constructed here:

        if (map_char_to_tracking[s[i]].char_count_in_string == 1)

This is a bug, because the default initialisation can leave any value in its char_count_in_string field (we're probably getting away with 0 because the list is allocating nodes in previously unused memory, but we can't rely on that).

Instead we should find() the appropriate node, or perhaps try_emplace() a suitable zero value. If we correctly use absence from the list as indicator of "never seen", then we only need a boolean to distinguish "seen once" from "seen multiple times". In fact, we don't even need that - when seen a second time, we can just replace the char_index_in_original_string with a sentinel value to indicate that.

---

I don't think we need the unique_chars set - we have the information in the map, and just need to extract it appropriately.

I would do that by having a view on the map that filters out the "seen twice or more" elements, then we can use std::ranges::min over the positions.

---

Unordered map is probably less efficient than plain std::map here (though we'd need a reasonable-sized benchmark to prove that).

---

Fixing the above problems, and using shorter names, we get a much simpler function using the same principles:

#include <algorithm>
#include <map>
#include <ranges>
#include <string>

std::size_t first_unique_char_index(const std::string& s)
{
    if (s.empty()) {
        return std::string::npos;
    }

    // Map from char to where it's first seen, or to 'npos' if seen more than once.
    std::map<char, std::size_t> first_seen;

    for (std::size_t i = 0;  i < s.size();  ++i) {
        auto [iter, is_new] = first_seen.try_emplace(s[i], i);
        if (!is_new) {
            iter->second = std::string::npos;
        }
    }

    return std::ranges::min(first_seen | std::views::values);
}

---

The function could be made more general as a template, so that it could work on other string types (such as string literals, or wide strings):

#include <algorithm>
#include <map>
#include <ranges>
#include <string_view>

std::size_t first_unique_char_index(auto const& input)
{
    const std::basic_string_view s{input};
    if (s.empty()) {
        return std::string::npos;
    }

    // Map from char to where it's first seen, or to 'npos' if seen
    // more than once.
    using char_type = decltype(s)::value_type;
    std::map<char_type, std::size_t> first_seen;

    for (std::size_t i = 0;  i < s.size();  ++i) {
        auto [iter, is_new] = first_seen.try_emplace(s[i], i);
        if (!is_new) {
            iter->second = std::string::npos;
        }
    }

    return std::ranges::min(first_seen | std::views::values);
}

Take care to observe that extracting single characters for strings doesn't make sense for string types not having a 1-to-1 correspondence with abstract characters - e.g. UTF-8 and UTF-16 strings. Those really ought to be converted to UCS-4.

---

The tests don't need to flush (with std::endl()) every line of output - just terminate with plain '\n'.

The tests would be better if they were self-checking - i.e. the program should return 0 if all tests produce the expected result, and non-zero if any of them fail.

It's good that we have tests for a selection of different cases (empty input, and with 0 or 1 unique characters). We need another test such as "mazaba" to demonstrate that we return the first unique character in the string, rather than the first or last alphabetically.

I prefer to put the trivial tests (empty string) first in the test set. That helps introduce the reader to the function's constraints as early as possible.