Longest substring without repeating characters

Input: “ABCBC”
Output: 3
Explanation: The longest substring without repeating characters is “ABC”

Input: “AAA”
Output: 1
Explanation: The longest substring without repeating characters is “A”

Input: “GEEKSFORGEEKS”
Output: 7 
Explanation: The longest substrings without repeating characters are “EKSFORG” and “KSFORGE”, with lengths of 7.

Table of Content

• [Naive Approach] Consider substrings starting from every index – O(n ^ 2) Time and O(1) Space
• [Expected Approach – 1] Using Sliding Window of Distinct Characters – O(n) Time and O(1) Space
• [Expected Approach – 2] Using Last Index of Each Character – O(n) Time and O(1) Space

[Naive Approach] Consider substrings starting from every index – O(n ^ 2) Time and O(1) Space

Starting from every index and maximum of all such lengths will be our response; we mostly locate length of longest substring with unique characters.

We build a new visited array of size 256 (We can also use a hash set, but a visited array would be better because we know that the character set is 256 in most of the cases) to keep track of included characters in the substring in order to ascertain the length of the longest substring with distinct characters starting from an index.

C++

// C++ program to find the length of the longest 
// substring without repeating characters

#include <bits/stdc++.h>
using namespace std;

int longestUniqueSubstr(string& s) {
    int n = s.size();
    int res = 0;

    for (int i = 0; i < n; i++) {

        // Initializing all characters as not visited
        vector<bool> visited(256, false);

        for (int j = i; j < n; j++) {

            // If current character is visited
            // Break the loop
            if (visited[s[j]] == true)
                break;

            // Else update the result if this window is larger,
            // and mark current character as visited.
            else {
                res = max(res, j - i + 1);
                visited[s[j]] = true;
            }
        }
    }
    return res;
}

int main() {
    string s = "geeksforgeeks";
    cout << longestUniqueSubstr(s);
    return 0;
}

C

// C program to find the length of the longest 
// substring without repeating characters

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int longestUniqueSubstr(char* s) {
    int n = strlen(s);
    int res = 0;

    for (int i = 0; i < n; i++) {
      
        // Initializing all characters as not visited
        bool visited[256] = { false };

        for (int j = i; j < n; j++) {
          
            // If current character is visited, 
              // break the loop
            if (visited[s[j]]) {
                break;
            }
              
            // Else update the result if this window is larger,
            // and mark current character as visited.
            else {
                if (res < j - i + 1)
                    res = j - i + 1;
                visited[s[j]] = true;
            }
        }
    }
    return res;
}

int main() {
    char s[] = "geeksforgeeks";
    printf("%d\n", longestUniqueSubstr(s));
    return 0;
}

Java

// Java program to find the length of the longest 
// substring without repeating characters

import java.util.*;

public class GfG {
    
    // Function to find the length of the longest 
      // substring without repeating characters
    static int longestUniqueSubstr(String s) {
        int n = s.length();
        int res = 0;

        for (int i = 0; i < n; i++) {

            // Initializing all characters as not visited
            boolean[] visited = new boolean[256];

            for (int j = i; j < n; j++) {

                // If current character is visited, 
                  // Break the loop
                if (visited[s.charAt(j)]) {
                    break;
                } 
                  else {
                  
                    // Else update the result if this 
                    // window is larger, and mark current 
                      // character as visited.
                    res = Math.max(res, j - i + 1);
                    visited[s.charAt(j)] = true;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "geeksforgeeks";
        System.out.println(longestUniqueSubstr(s));
    }
}

Python

# Python program to find the length of the longest 
# substring without repeating characters

def longestUniqueSubstr(s):
    n = len(s)
    res = 0

    for i in range(n):

        # Initializing all characters as not visited
        visited = [False] * 256

        for j in range(i, n):

            # If current character is visited
            # Break the loop
            if visited[ord(s[j])] == True:
                break

            # Else update the result if this window is larger,
            # and mark current character as visited.
            else:
                res = max(res, j - i + 1)
                visited[ord(s[j])] = True

    return res

if __name__ == "__main__":
    s = "geeksforgeeks"
    print(longestUniqueSubstr(s))

JavaScript

// JavaScript program to find the length of the longest 
// substring without repeating characters

function longestUniqueSubstr(s) {
    let n = s.length;
    let res = 0;

    for (let i = 0; i < n; i++) {
        // Initializing all characters as not visited
        let visited = new Array(256).fill(false);

        for (let j = i; j < n; j++) {
            // If current character is visited
            // Break the loop
            if (visited[s.charCodeAt(j)] === true) {
                break;
            } else {
                // Else update the result if this window is larger,
                // and mark current character as visited.
                res = Math.max(res, j - i + 1);
                visited[s.charCodeAt(j)] = true;
            }
        }
    }
    return res;
}

const s = "geeksforgeeks";
console.log(longestUniqueSubstr(s));

Output

7