Question

Given a string, return the length of the longest substring without repeating characters.

Solution

This question is very commonly asked in SDET and Software Engineering Interviews to test your understanding about sliding window technique.

Understanding the problem

You're given a string, and your task is to find the length of the longest substring within that string that doesn't contain any repeating characters.

Example: Let's take an example string: "abcabcbb".

The longest substring without repeating characters in this string is "abc", which has a length of 3.

Approach

Let's try to break this problem into smaller parts.

Broken Problem #1 - We have to first find the longest substring

This is very similar to how we find max number in an array, where we create a max and current variable and we compare them on each iteration.

We have to store a longest_string and a current_string variable and compare them in each iteration.

On each iteration we can add current_char to current_string and update the value of longest_string when current_string length is greater than longest_string

current_substring = ""
longest_substring = ""

Broken Problem #2 - Longest substring can't contain any duplicate values.

We need a way to check if the current_char is already present in our current_string. If it is present then we can not add again. We can handle this using a set.

char_set = []

We can add the current_char in this set too when we are adding it to current_string. Such that at any time, values in set will be same as current_string

eg. char_set = ['a', 'b', 'c'] then current_string = "abc"

If our current_char is already in our set then we need to keep removing the first element from our current_string and char_set no duplicate characters are remaining.

Example - If current_string = "abc" and next character is 'c', so current_string will be "abcc"

We will remove 'a' first, and observe that current_string "bcc" still has repeating character.

We will then remove 'b' and observe that current_string "cc" still has repeating character

Finally we will remove 'c' and observe that it is now unique.

We can keep a start and end pointer to keep track of what is the first and last index of our current_string. Each time we add a character, we increment end and each time we remove a character, we increment start.

Let's try to code this now.

Python Program for Length of longest substring without repeating characters

def lengthOfLongestSubstring(s):
    char_set = []
    current_substring = ""
    longest_substring = ""
    start = 0
    end = 0
    length = len(s)

    while end < length:
        current_char = s[end]
        first_char = s[start]
        if current_char not in char_set:
            #Adding current_char/s[end] to both set and substring
            char_set.append(current_char)
            current_substring += current_char
            if len(current_substring) > len(longest_substring):
                #Update substring in case current_substring is longer
                longest_substring = current_substring
            end += 1
        else:
            #In case current_char/s[end] is already present in set & substring
            current_substring = current_substring[1:] #Remove first character
            char_set.remove(first_char) #Remove first_char/s[start] from set
            start += 1

    return len(longest_substring)

Java Program for Length of longest substring without repeating characters

import java.util.HashSet;

public class Main {
    public static int lengthOfLongestSubstring(String s) {
        HashSet<Character> charSet = new HashSet<>();
        StringBuilder currentSubstring = new StringBuilder();
        String longestSubstring = "";
        int start = 0;
        int end = 0;
        int length = s.length();

        while (end < length) {
            char currentChar = s.charAt(end);
            char firstChar = s.charAt(start);
            if (!charSet.contains(currentChar)) {
                // Adding currentChar/s[end] to both set and substring
                charSet.add(currentChar);
                currentSubstring.append(currentChar);
                if (currentSubstring.length() > longestSubstring.length()) {
                    // Update substring in case currentSubstring is longer
                    longestSubstring = currentSubstring.toString();
                }
                end++;
            } else {
                // In case currentChar/s[end] is already present in set & substring
                currentSubstring.deleteCharAt(0); // Remove first character
                charSet.remove(firstChar); // Remove firstChar/s[start] from set
                start++;
            }
        }

        return longestSubstring.length();
    }

    public static void main(String[] args) {
        String input = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(input)); // Output: 3
    }
}

C++ Program for Length of longest substring without repeating characters

#include <iostream>
#include <unordered_set>
#include <string>

using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_set<char> charSet;
    string currentSubstring = "";
    string longestSubstring = "";
    int start = 0;
    int end = 0;
    int length = s.length();

    while (end < length) {
        char currentChar = s[end];
        char firstChar = s[start];
        if (charSet.find(currentChar) == charSet.end()) {
            // Adding currentChar/s[end] to both set and substring
            charSet.insert(currentChar);
            currentSubstring += currentChar;
            if (currentSubstring.length() > longestSubstring.length()) {
                // Update substring in case currentSubstring is longer
                longestSubstring = currentSubstring;
            }
            end++;
        } else {
            // In case currentChar/s[end] is already present in set & substring
            currentSubstring.erase(0, 1); // Remove first character
            charSet.erase(firstChar); // Remove firstChar/s[start] from set
            start++;
        }
    }

    return longestSubstring.length();
}

int main() {
    string input = "abcabcbb";
    cout << lengthOfLongestSubstring(input) << endl; // Output: 3
    return 0;
}