c++ - Is there a struct function for finding the longest and not-repeating length substring within a string?

Question

The aim of the function is to find out the longest and not repeating substring, so I need to find out the start position of the substring and the length of it. The thing I'm struggling with is the big O notation should be O(n). Therefore I cannot use nested for loops to check whether each letter is repeated. I created a struct function like this but I don't know how to continue:

struct Answer {             
    int start;              
    int length;
};

Answer findsubstring(char *string){
    Answer sub={0, 0}

    for (int i = 0; i < strlen(string); i++) {
        
    }
    return (sub)
}

For example, the input is HelloWorld, and the output should be World.The length is 5. If the input isabagkfleoKi, then the output is bagkfleoKi. The length is 10. Also, if the length of two strings is the same, pick the latter one.

question from:https://stackoverflow.com/questions/65857218/is-there-a-struct-function-for-finding-the-longest-and-not-repeating-length-subs

Answer 1

Use a std::unordered_map<char, size_t> to store the indices past the last occurance of a certain char.

Keep the currently best match as well as the match you currently test. Iterating through the chars of the input result in 2 cases you need to handle:

1. the char already occured and the last occurance of the char requires you to move the start of the potential match to avoid the char from occuring twice: Update the answer with the match ending just before the current char, if that's better than the current answer.
2. Otherwise: Just update the map

void printsubstring(const char* input)
{
    std::unordered_map<char, size_t> lastOccurances;

    Answer answer{ 0, 0 };

    size_t currentPos = 0;
    size_t currentStringStart = 0;

    char c;

    while ((c = input[currentPos]) != 0)
    {
        auto entry = lastOccurances.insert({ c, currentPos + 1 });

        if (!entry.second)
        {
            if (currentStringStart < entry.first->second && currentPos - currentStringStart > answer.length)
            {
                // need to move the start of the potential answer
                // -> check, if the match up to the char before the current char was better
                answer.start = currentStringStart;
                answer.length = currentPos - currentStringStart;
                currentStringStart = entry.first->second;
            }
            
            entry.first->second = currentPos + 1;
        }
        ++currentPos;
    }

    // check the match ending at the end of the string
    if (currentPos - currentStringStart > answer.length)
    {
        answer.start = currentStringStart;
        answer.length = currentPos - currentStringStart;
    }

    std::cout << answer.start << ", " << answer.length << std::endl;
    std::cout << std::string_view(input + answer.start, answer.length) << std::endl;
}