Question

How to find the longest substring without repeating characters in C++

Answer 1

#include <iostream>
#include <string>
#include <vector>

/*
 * Finds the longest substring without repeating characters.
 * This version keeps a presence table and shrinks the window
 * by clearing characters until the duplicate is removed.
 *
 * Time complexity: O(n)
 */
std::string longestUniqueSubstringASCII(const std::string& s) {
    std::vector<bool> seen(256, false);   // ASCII presence table

    int left = 0, right = 0;
    int bestLeft = 0, bestRight = 0;

    while (right < static_cast<int>(s.size())) {
        unsigned char c = s[right];

        if (seen[c]) {
            // Shrink window until we remove the duplicate
            while (s[left] != c) {
                seen[static_cast<unsigned char>(s[left])] = false;
                left++;
            }
            left++; // skip the duplicate itself
        } else {
            seen[c] = true;

            if (right - left > bestRight - bestLeft) {
                bestLeft = left;
                bestRight = right;
            }
        }

        right++;
    }

    return s.substr(bestLeft, bestRight - bestLeft + 1);
}

int main() {
    std::string str = "xwwwqfwwxqwyq";

    std::string result = longestUniqueSubstringASCII(str);

    std::cout << "Input: " << str << "\n";
    std::cout << "Longest substring without repeating characters: " << result << "\n";
}


/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <string>
#include <vector>

/*
 * Finds the longest substring without repeating characters.
 * Uses a sliding window and a table of last-seen indexes.
 *
 * - lastSeen[c] stores the most recent index of character c.
 * - left/right define the current window.
 * - When a duplicate appears inside the window, move left forward.
 *
 * Time complexity: O(n)
 */
std::string longestUniqueSubstring(const std::string& s) {
    std::vector<int> lastSeen(256, -1);   // ASCII table
    int left = 0;
    int bestStart = 0;
    int bestLength = 0;

    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        unsigned char c = s[right];

        // If character was seen inside the current window, move left
        if (lastSeen[c] >= left) {
            left = lastSeen[c] + 1;
        }

        // Update last-seen index
        lastSeen[c] = right;

        // Check if this window is the best so far
        int windowLength = right - left + 1;
        if (windowLength > bestLength) {
            bestLength = windowLength;
            bestStart = left;
        }
    }

    return s.substr(bestStart, bestLength);
}

int main() {
    std::string str = "xwwwqfwwxqwyq";

    std::string result = longestUniqueSubstring(str);

    std::cout << "Input: " << str << "\n";
    std::cout << "Longest substring without repeating characters: " << result << "\n";
}



/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals