Longest Substring Without Repeating Characters - CPP Solution

1. Introduction

In this post, we explore a common algorithmic challenge in string processing: finding the length of the longest substring without repeating characters. This problem is a staple in coding interviews and a great way to understand hash tables and window sliding techniques in C++.

Problem

Given a string 's', find the length of the longest substring without repeating characters. For example, in the string "abcabcbb", the longest substring without repeating characters is "abc", with a length of 3.

2. Solution Steps

1. Utilize a sliding window approach to keep track of the current substring.

2. Maintain a hash map to store characters and their latest indices in the window.

3. Expand the right end of the window and include new characters.

4. If a repeat character is encountered, move the left end of the window.

5. Continuously update the maximum length of the substring found so far.

6. Iterate through the string to apply this process and find the maximum length.

3. Code Program

#include <iostream>
#include <unordered_map>
using namespace std;

// Function to find the length of the longest substring without repeating characters
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> charMap; // Hash map for character indices
    int left = 0, maxLength = 0; // Left pointer and max length tracker

    for (int right = 0; right < s.length(); right++) {
        if (charMap.find(s[right]) != charMap.end()) {
            // Move left pointer if repeat character found
            left = max(left, charMap[s[right]] + 1);
        }
        charMap[s[right]] = right; // Update or add character index
        maxLength = max(maxLength, right - left + 1); // Update max substring length
    }
    return maxLength; // Return the longest length found
}

int main() {
    string str = "abcabcbb";
    cout << "Length of the longest substring: " << lengthOfLongestSubstring(str) << endl;
    return 0;
}

Output:

Length of the longest substring: 3

Explanation:

1. The input string "abcabcbb" is processed character by character.

2. Initially, 'a', 'b', and 'c' form a substring without repeat.

3. Upon encountering the second 'a', the left pointer moves past the first 'a'.

4. This process repeats, ensuring no characters are repeated in the current window.

5. The maximum length of such a substring is calculated as 3, corresponding to "abc".