CODEWITHSUNDEEP
c++
Yoni
Yoni

Reputation: 11

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

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.

Upvotes: 0

Views: 91

Answers (2)

Ted Lyngmo
Ted Lyngmo

Reputation: 117258

I'll outline one possible solution.

  1. You'll need two loops. One for pointing at the start of the substring and one that points at the end. 
    auto stringlen = std::strlen(string);
for(size_t beg = 0; beg < stringlen - sub.length; ++beg) {
    // See point 2.
    for(size_t end = beg; end < stringlen; ++end) {
        // See point 3.
    }
}
  2. Create a "blacklist" of characters already seen in the substring. 
    bool blacklist[1 << CHAR_BIT]{}; // zero initialized
  3. Check if the current end character is already in the blacklist and break out of the loop if it is, otherwise, put it in the blacklist. 
    if(blacklist[ static_cast<unsigned char>(string[end]) ]) break;
else {
    blacklist[ static_cast<unsigned char>(string[end]) ] = true;
    // See point 4.
}
  4. Check if the length of the current substring (end - beg + 1) is greater than the longest you currently have (sub.length). If it is longer, store sub.start = beg and sub.length = end - beg + 1

Demo and Demo using a bitset<> instead

Upvotes: 0

fabian
fabian

Reputation: 82461

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;
}

Upvotes: 1

Related Questions