Length of the longest substring without repeating characters

Last Updated : 29 Feb, 2024

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

Example:

Example 1:
Input: “ABCDEFGABEF”
Output: 7
Explanation: The longest substring without repeating characters are “ABCDEFG”, “BCDEFGA”, and “CDEFGAB” with lengths of 7

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

Length of the longest substring without repeating characters using Sliding Window in O(n³) time:

Consider all substrings one by one and check for each substring whether it contains all unique characters or not. There will be n*(n+1)/2 substrings. Whether a substring contains all unique characters or not can be checked in linear time by scanning it from left to right and keeping a map of visited characters.

Below is the implementation of above approach:

C++

// C++ program to find the length of the longest substring
// without repeating characters
#include <bits/stdc++.h>
using namespace std;
 
// This function returns true if all characters in str[i..j]
// are distinct, otherwise returns false
bool areDistinct(string str, int i, int j)
{
 
    // Note : Default values in visited are false
    vector<bool> visited(256);
 
    for (int k = i; k <= j; k++) {
        if (visited[str[k]] == true)
            return false;
        visited[str[k]] = true;
    }
    return true;
}
 
// Returns length of the longest substring
// with all distinct characters.
int longestUniqueSubsttr(string str)
{
    int n = str.size();
    int res = 0; // result
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            if (areDistinct(str, i, j))
                res = max(res, j - i + 1);
    return res;
}
 
// Driver code
int main()
{
    string str = "geeksforgeeks";
    cout << "The input string is " << str << endl;
    int len = longestUniqueSubsttr(str);
    cout << "The length of the longest non-repeating "
            "character substring is "
         << len;
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

C

// C program to find the length of the longest substring
// without repeating characters
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
 
// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}
 
// This function returns true if all characters in str[i..j]
// are distinct, otherwise returns false
bool areDistinct(char str[], int i, int j)
{
 
    // Note : Default values in visited are false
    bool visited[256];
    for (int i = 0; i < 256; i++)
        visited[i] = 0;
 
    for (int k = i; k <= j; k++) {
        if (visited[str[k]] == true)
            return false;
        visited[str[k]] = true;
    }
    return true;
}
 
// Returns length of the longest substring
// with all distinct characters.
int longestUniqueSubsttr(char str[])
{
    int n = strlen(str);
    int res = 0; // result
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            if (areDistinct(str, i, j))
                res = max(res, j - i + 1);
    return res;
}
 
// Driver code
int main()
{
    char str[] = "geeksforgeeks";
    printf("The input string is %s \n", str);
    int len = longestUniqueSubsttr(str);
    printf("The length of the longest non-repeating "
           "character substring is %d",
           len);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

Java

// Java program to find the length of the
// longest substring without repeating
// characters
import java.io.*;
import java.util.*;
 
class GFG {
 
    // This function returns true if all characters in
    // str[i..j] are distinct, otherwise returns false
    public static Boolean areDistinct(String str, int i,
                                      int j)
    {
 
        // Note : Default values in visited are false
        boolean[] visited = new boolean[256];
 
        for (int k = i; k <= j; k++) {
            if (visited[str.charAt(k)] == true)
                return false;
 
            visited[str.charAt(k)] = true;
        }
        return true;
    }
 
    // Returns length of the longest substring
    // with all distinct characters.
    public static int longestUniqueSubsttr(String str)
    {
        int n = str.length();
 
        // Result
        int res = 0;
 
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                if (areDistinct(str, i, j))
                    res = Math.max(res, j - i + 1);
 
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        System.out.println("The input string is " + str);
 
        int len = longestUniqueSubsttr(str);
 
        System.out.println("The length of the longest "
                           + "non-repeating character "
                           + "substring is " + len);
    }
}
 
// This code is contributed by akhilsaini

C#

// C# program to find the length of the
// longest substring without repeating
// characters
using System;
 
class GFG {
 
    // This function returns true if all characters in
    // str[i..j] are distinct, otherwise returns false
    public static bool areDistinct(string str, int i, int j)
    {
 
        // Note : Default values in visited are false
        bool[] visited = new bool[256];
 
        for (int k = i; k <= j; k++) {
            if (visited[str[k]] == true)
                return false;
 
            visited[str[k]] = true;
        }
        return true;
    }
 
    // Returns length of the longest substring
    // with all distinct characters.
    public static int longestUniqueSubsttr(string str)
    {
        int n = str.Length;
 
        // Result
        int res = 0;
 
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                if (areDistinct(str, i, j))
                    res = Math.Max(res, j - i + 1);
 
        return res;
    }
 
    // Driver code
    public static void Main()
    {
        string str = "geeksforgeeks";
        Console.WriteLine("The input string is " + str);
 
        int len = longestUniqueSubsttr(str);
 
        Console.WriteLine("The length of the longest "
                          + "non-repeating character "
                          + "substring is " + len);
    }
}
 
// This code is contributed by sanjoy_62

Javascript

// JavaScript program to find the length of the
// longest substring without repeating
// characters
// This function returns true if all characters in
// str[i..j] are distinct, otherwise returns false
function areDistinct(str, i, j)
{
     
    // Note : Default values in visited are false
    var visited = new Array(256);
 
    for(var k = i; k <= j; k++)
    {
        if (visited[str.charAt(k) ] == true)
            return false;
             
        visited[str.charAt(k)] = true;
    }
    return true;
}
 
// Returns length of the longest substring
// with all distinct characters.
function longestUniqueSubsttr(str)
{
    var n = str.length;
     
    // Result
    var res = 0; 
     
    for(var i = 0; i < n; i++)
        for(var j = i; j < n; j++)
            if (areDistinct(str, i, j))
                res = Math.max(res, j - i + 1);
                 
    return res;
}
 
// Driver code
    var str = "geeksforgeeks";
    console.log("The input string is " + str);
 
    var len = longestUniqueSubsttr(str);
     
    console.log("The length of the longest " +
                       "non-repeating character " + 
                       "substring is " + len);
 
// This code is contributed by shivanisinghss2110.

Python3

# Python3 program to find the length
# of the longest substring without
# repeating characters
 
# This function returns true if all
# characters in str[i..j] are
# distinct, otherwise returns false
 
 
def areDistinct(str, i, j):
 
    # Note : Default values in visited are false
    visited = [0] * (256)
 
    for k in range(i, j + 1):
        if (visited[ord(str[k])] == True):
            return False
 
        visited[ord(str[k])] = True
 
    return True
 
# Returns length of the longest substring
# with all distinct characters.
 
 
def longestUniqueSubsttr(str):
 
    n = len(str)
 
    # Result
    res = 0
 
    for i in range(n):
        for j in range(i, n):
            if (areDistinct(str, i, j)):
                res = max(res, j - i + 1)
 
    return res
 
 
# Driver code
if __name__ == '__main__':
 
    str = "geeksforgeeks"
    print("The input is ", str)
 
    len = longestUniqueSubsttr(str)
    print("The length of the longest "
          "non-repeating character substring is ", len)
 
# This code is contributed by mohit kumar 29

Output

The input string is geeksforgeeks
The length of the longest non-repeating character substring is 7

Time Complexity: O(n^3) since we are processing n^2 substrings with maximum length n.
Auxiliary Space: O(1)

Length of the longest substring without repeating characters using Sliding Window in O(n²) time:

For each index i, find the the length of longest substring without repeating characters starting at index i. This can be done by starting at index i, and iterating until the end of the string, if a repeating character is found before the end of string we will break else update the answer if the current substring is larger.

Below is the implementation of above approach:

C++

// C++ program to find the length of the longest substring
// without repeating characters
#include <bits/stdc++.h>
using namespace std;
 
int longestUniqueSubsttr(string str)
{
    int n = str.size();
    int res = 0; // result
 
    for (int i = 0; i < n; i++) {
 
        // Note : Default values in visited are false
        vector<bool> visited(256);
 
        for (int j = i; j < n; j++) {
 
            // If current character is visited
            // Break the loop
            if (visited[str[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[str[j]] = true;
            }
        }
 
        // Remove the first character of previous
        // window
        visited[str[i]] = false;
    }
    return res;
}
 
// Driver code
int main()
{
    string str = "geeksforgeeks";
    cout << "The input string is " << str << endl;
    int len = longestUniqueSubsttr(str);
    cout << "The length of the longest non-repeating "
            "character substring is "
         << len;
    return 0;
}

Java

// Java program to find the length of the
// longest substring without repeating
// characters
import java.io.*;
import java.util.*;
 
class GFG {
 
    public static int longestUniqueSubsttr(String str)
    {
        int n = str.length();
 
        // Result
        int res = 0;
 
        for (int i = 0; i < n; i++) {
 
            // Note : Default values in visited are false
            boolean[] visited = new boolean[256];
 
            for (int j = i; j < n; j++) {
 
                // If current character is visited
                // Break the loop
                if (visited[str.charAt(j)] == true)
                    break;
 
                // Else update the result if
                // this window is larger, and mark
                // current character as visited.
                else {
                    res = Math.max(res, j - i + 1);
                    visited[str.charAt(j)] = true;
                }
            }
 
            // Remove the first character of previous
            // window
            visited[str.charAt(i)] = false;
        }
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        System.out.println("The input string is " + str);
 
        int len = longestUniqueSubsttr(str);
        System.out.println("The length of the longest "
                           + "non-repeating character "
                           + "substring is " + len);
    }
}
 
// This code is contributed by akhilsaini

C#

// C# program to find the length of the
// longest substring without repeating
// characters
using System;
 
class GFG {
 
    static int longestUniqueSubsttr(string str)
    {
        int n = str.Length;
 
        // Result
        int res = 0;
 
        for (int i = 0; i < n; i++) {
 
            // Note : Default values in visited are false
            bool[] visited = new bool[256];
 
            // visited = visited.Select(i =>
            // false).ToArray();
            for (int j = i; j < n; j++) {
 
                // If current character is visited
                // Break the loop
                if (visited[str[j]] == true)
                    break;
 
                // Else update the result if
                // this window is larger, and mark
                // current character as visited.
                else {
                    res = Math.Max(res, j - i + 1);
                    visited[str[j]] = true;
                }
            }
 
            // Remove the first character of previous
            // window
            visited[str[i]] = false;
        }
        return res;
    }
 
    // Driver code
    static void Main()
    {
        string str = "geeksforgeeks";
        Console.WriteLine("The input string is " + str);
 
        int len = longestUniqueSubsttr(str);
        Console.WriteLine("The length of the longest "
                          + "non-repeating character "
                          + "substring is " + len);
    }
}
 
// This code is contributed by divyeshrabadiya07

Javascript

// JavaScript program to find the length of the 
// longest substring without repeating
// characters
 
function longestUniqueSubsttr(str)
{
    var n = str.length;
     
    // Result
    var res = 0;
     
    for(var i = 0; i < n; i++)
    {
         
        // Note : Default values in visited are false
        var visited = new Array(256);
         
        for(var j = i; j < n; j++)
        {
             
            // If current character is visited
            // Break the loop
            if (visited[str.charCodeAt(j)] == true)
                break;
 
            // Else update the result if
            // this window is larger, and mark
            // current character as visited.
            else
            {
                res = Math.max(res, j - i + 1);
                visited[str.charCodeAt(j)] = true;
            }
        }
    }
    return res;
}
 
// Driver code
    var str = "geeksforgeeks";
    console.log("The input string is " + str);
 
    var len = longestUniqueSubsttr(str);
    console.log("The length of the longest " +
                       "non-repeating character " +
                       "substring is " + len);
  
// This code is contributed by shivanisinghss2110
// This code is edited by ziyak9803

Python3

# Python3 program to find the
# length of the longest substring
# without repeating characters
 
 
def longestUniqueSubsttr(str):
 
    n = len(str)
 
    # Result
    res = 0
 
    for i in range(n):
 
        # Note : Default values in
        # visited are false
        visited = [0] * 256
 
        for j in range(i, n):
 
            # If current character is visited
            # Break the loop
            if (visited[ord(str[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(str[j])] = True
 
        # Remove the first character of previous
        # window
        visited[ord(str[i])] = False
 
    return res
 
 
# Driver code
str = "geeksforgeeks"
print("The input is ", str)
 
len = longestUniqueSubsttr(str)
print("The length of the longest "
      "non-repeating character substring is ", len)
 
# This code is contributed by sanjoy_62

Output

The input string is geeksforgeeks
The length of the longest non-repeating character substring is 7

Time Complexity: O(n^2), (The outer loop runs in O(n) time, and the inner loop runs in O(n) in the worst case (considering all unique characters), resulting in a total time complexity of O(n^2).)
Auxiliary Space: O(1)

Length of the longest substring without repeating characters using Binary Search on Answer:

The idea is to check if a substring of a certain size “mid” is valid (A size mid is valid if there exists atleast one substring of size mid which contains all unique characters ), then all the size less than “mid” will also be valid. Similarly, if a substring of size “mid” is not valid(A size mid is not valid if there does not exists any substring of size mid which contains all unique characters ), then all the size larger than “mid” will also not be valid. This allows us to apply binary search effectively.

Follow the steps below to solve the problem:

Initialize low and high as 1 and string length respectively denoting the minimum and maximum possible answer.
For any value mid check if there is any substring of length mid in the string that contains all the unique characters.
If any such substring of length exists then update the value of answer with mid store the starting index of that substring and update low to mid+1 and, check for substrings having lengths larger than mid.
Otherwise, if any such substring does not exist then update high to mid-1 and, check for substrings having lengths smaller than mid.

Below is the implementation of above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
 
// Function to check if any substring of length mid contains
// all unique characters 
bool isValid(string& s, int mid)
{
    // Count the frequency of each character in the pattern
    int count[256] = { 0 };
 
 
    bool found = false;
 
 
    // Stores the number of distict charcters in a substring of size
    // mid 
    int distinct = 0;
   
    for (int i = 0; i < s.size(); i++) {
        count[s[i]]++;
        if (count[s[i]] == 1) {
            distinct++;
        }
        if (i >= mid) {
            count[s[i - mid]]--;
            if (count[s[i - mid]] == 0) {
                distinct--;
            }
        }
        if (i >= mid - 1) {
 
            // Substring of length mid found which contains
            // all the unique characters 
            if (distinct == mid) {
                found = true;
            }
        }
    }
 
    return found;
}
 
// Function to find the longest substring containing nom-repeating
// characters 
int longestUniqueSubsttr(string& s)
{
    int len = s.length();
 
    int ans = INT_MAX;
 
    // Lower bound and Upper Bound for Binary Serach
    int low_bound = 1, high_bound = len;
 
 
    // Applying Binary Search on answer
    while (low_bound <= high_bound) {
        int mid = (low_bound + high_bound) / 2;
         
 
        // If a substring of length mid is found which
        // contains all unique characters then
        // update low_bound otherwise update
        // high_bound
        if (isValid(s,mid)) {
              ans=mid;
            low_bound = mid + 1;
        }
     
        else {
            high_bound = mid - 1;
        }
    }
 
    return ans;
}
 
 
 
// Driver code
int main()
{
    string str = "geeksforgeeks";
    cout << "The input string is " << str << endl;
    int len = longestUniqueSubsttr(str);
    cout << "The length of the longest non-repeating "
            "character substring is "
         << len;
    return 0;
}

Java

import java.util.Arrays;
 
public class Main {
    // Function to check if any substring of length mid contains
    // all unique characters
    static boolean isValid(String s, int mid) {
        int[] count = new int[256];
        boolean found = false;
        int distinct = 0;
 
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
            if (count[s.charAt(i)] == 1) {
                distinct++;
            }
            if (i >= mid) {
                count[s.charAt(i - mid)]--;
                if (count[s.charAt(i - mid)] == 0) {
                    distinct--;
                }
            }
            if (i >= mid - 1 && distinct == mid) {
                found = true;
            }
        }
 
        return found;
    }
 
    // Function to find the longest substring containing non-repeating
    // characters
    static int longestUniqueSubsttr(String s) {
        int len = s.length();
        int ans = Integer.MAX_VALUE;
 
        // Lower bound and Upper Bound for Binary Search
        int lowBound = 1, highBound = len;
 
        // Applying Binary Search on answer
        while (lowBound <= highBound) {
            int mid = (lowBound + highBound) / 2;
 
            // If a substring of length mid is found which
            // contains all unique characters then
            // update lowBound otherwise update
            // highBound
            if (isValid(s, mid)) {
                ans = mid;
                lowBound = mid + 1;
            } else {
                highBound = mid - 1;
            }
        }
 
        return ans;
    }
 
    // Driver code
    public static void main(String[] args) {
        String str = "geeksforgeeks";
        System.out.println("The input string is " + str);
        int len = longestUniqueSubsttr(str);
        System.out.println("The length of the longest non-repeating "
                + "character substring is " + len);
    }
}

C#

using System;
 
class GFG
{
    // Function to check if any substring of length mid contains
    // all unique characters 
    static bool IsValid(string s, int mid)
    {
        // Count the frequency of each character in the pattern
        int[] count = new int[256];
        bool found = false;
        // Stores the number of distinct characters in a substring of 
      // size mid 
        int distinct = 0;
        for (int i = 0; i < s.Length; i++)
        {
            count[s[i]]++;
            if (count[s[i]] == 1)
            {
                distinct++;
            }
            if (i >= mid)
            {
                count[s[i - mid]]--;
                if (count[s[i - mid]] == 0)
                {
                    distinct--;
                }
            }
            if (i >= mid - 1)
            {
                // Substring of length mid found which contains all the unique characters 
                if (distinct == mid)
                {
                    found = true;
                }
            }
        }
        return found;
    }
    // Function to find the longest substring containing 
  // non-repeating characters 
    static int LongestUniqueSubstring(string s)
    {
        int len = s.Length;
        int ans = int.MaxValue;
        // Lower bound and Upper Bound for Binary Search
        int lowBound = 1, highBound = len;
        // Applying Binary Search on answer
        while (lowBound <= highBound)
        {
            int mid = (lowBound + highBound) / 2;
            if (IsValid(s, mid))
            {
                ans = mid;
                lowBound = mid + 1;
            }
            else
            {
                highBound = mid - 1;
            }
        }
        return ans;
    }
    // Driver code
    static void Main(string[] args)
    {
        string str = "geeksforgeeks";
        Console.WriteLine("The input string is " + str);
        int len = LongestUniqueSubstring(str);
        Console.WriteLine("The length of the longest non-repeating " +
            "character substring is " + len);
    }
}

Javascript

// Function to check if any substring of length mid contains
// all unique characters 
function isValid(s, mid) {
    // Count the frequency of each character in the pattern
    let count = new Array(256).fill(0);
 
    let found = false;
 
    // Stores the number of distinct characters in a substring of size mid
    let distinct = 0;
 
    for (let i = 0; i < s.length; i++) {
        count[s.charCodeAt(i)]++;
        if (count[s.charCodeAt(i)] === 1) {
            distinct++;
        }
        if (i >= mid) {
            count[s.charCodeAt(i - mid)]--;
            if (count[s.charCodeAt(i - mid)] === 0) {
                distinct--;
            }
        }
        if (i >= mid - 1) {
            // Substring of length mid found which contains
            // all the unique characters 
            if (distinct === mid) {
                found = true;
            }
        }
    }
 
    return found;
}
 
// Function to find the longest substring containing non-repeating characters 
function longestUniqueSubsttr(s) {
    const len = s.length;
    let ans = Number.MAX_SAFE_INTEGER;
 
    // Lower bound and Upper Bound for Binary Search
    let low_bound = 1;
    let high_bound = len;
 
    // Applying Binary Search on answer
    while (low_bound <= high_bound) {
        const mid = Math.floor((low_bound + high_bound) / 2);
 
        // If a substring of length mid is found which
        // contains all unique characters, then update low_bound
        // otherwise update high_bound
        if (isValid(s, mid)) {
            ans = mid;
            low_bound = mid + 1;
        } else {
            high_bound = mid - 1;
        }
    }
 
    return ans;
}
 
// Driver code
const str = "geeksforgeeks";
console.log("The input string is " + str);
const len = longestUniqueSubsttr(str);
console.log("The length of the longest non-repeating " +
    "character substring is " + len);

Python3

def is_valid(s, mid):
    # Count the frequency of each character in the pattern
    count = [0] * 256
    found = False
 
    # Stores the number of distinct characters in a substring of size mid
    distinct = 0
 
    for i in range(len(s)):
        count[ord(s[i])] += 1
        if count[ord(s[i])] == 1:
            distinct += 1
        if i >= mid:
            count[ord(s[i - mid])] -= 1
            if count[ord(s[i - mid])] == 0:
                distinct -= 1
        if i >= mid - 1:
            # Substring of length mid found which contains all the unique characters
            if distinct == mid:
                found = True
 
    return found
 
def longest_unique_substring(s):
    length = len(s)
    ans = float('inf')
 
    # Lower bound and Upper Bound for Binary Search
    low_bound = 1
    high_bound = length
 
    # Applying Binary Search on answer
    while low_bound <= high_bound:
        mid = (low_bound + high_bound) // 2
 
        # If a substring of length mid is found which contains all unique characters
        # then update low_bound, otherwise update high_bound
        if is_valid(s, mid):
            ans = mid
            low_bound = mid + 1
        else:
            high_bound = mid - 1
 
    return ans
 
# Driver code
if __name__ == "__main__":
    input_str = "geeksforgeeks"
    print("The input string is", input_str)
    length = longest_unique_substring(input_str)
    print("The length of the longest non-repeating character substring is", length)
 
     
# This code is contributed by shivamgupta310570

Output

The input string is geeksforgeeks
The length of the longest non-repeating character substring is 7

Time Complexity: O(N*logN), where N is the length of string.
Auxiliary Space: O(1)

Length of the longest substring without repeating characters using Sliding Window:

Using this solution the problem can be solved in linear time using the window sliding technique.

Follow the steps below to solve the problem:

Intialize two pointers left and right with 0, which define the current window being considered.
The right pointer moves from left to right, extending the current window.
If the character at right pointer is not visited , it’s marked as visited.
If the character at right pointer is visited, it means there is a repeating character. The left pointer moves to the right while marking visited characters as false until the repeating character is no longer part of the current window.
The length of the current window (right - left + 1) is calculated and answer is updated accordingly.

Below is the implementation of above approach:

C++

#include <iostream>
#include <string>
using namespace std;
 
int longestUniqueSubsttr(string str)
{
    // if string length is 0
    if (str.length() == 0)
        return 0;
 
    // if string length 1
    if (str.length() == 1)
        return 1;
 
    // if string length is more than 2
    int maxLength = 0;
    bool visited[256] = { false };
 
    // left and right pointer of sliding window
    int left = 0, right = 0;
    while (right < str.length()) {
 
        // if character is visited
        if (visited[str[right]] == true) {
 
            // The left pointer moves to the right while
            // marking visited characters as false until the
            // repeating character is no longer part of the
            // current window.
            while (visited[str[right]] == true) {
 
                visited[str[left]] = false;
                left++;
            }
        }
 
        visited[str[right]] = true;
 
        // The length of the current window (right - left +
        // 1) is calculated and answer is updated
        // accordingly.
        maxLength = max(maxLength, (right - left + 1));
        right++;
    }
    return maxLength;
}
 
// Driver code
int main()
{
    string str = "geeksforgeeks";
    cout << "The input string is " << str << endl;
    int len = longestUniqueSubsttr(str);
    cout << "The length of the longest non-repeating "
            "character substring is "
         << len;
    return 0;
}

Java

import java.io.*;
 
class GFG {
    public static int longestUniqueSubsttr(String str)
    {
        // if string length is 0
        if (str.length() == 0)
            return 0;
 
        // if string length 1
        if (str.length() == 1)
            return 1;
 
        // if string length is more than 2
        int maxLength = 0;
        boolean[] visited = new boolean[256];
 
        // left and right pointer of sliding window
        int left = 0, right = 0;
        while (right < str.length()) {
 
            // if character is visited
            if (visited[str.charAt(right)]) {
 
                // The left pointer moves to the right while
                // marking visited characters as false until
                // the repeating character is no longer part
                // of the current window.
                while (visited[str.charAt(right)]) {
 
                    visited[str.charAt(left)] = false;
                    left++;
                }
            }
 
            visited[str.charAt(right)] = true;
 
            // The length of the current window (right -
            // left + 1) is calculated and answer is updated
            // accordingly.
            maxLength
                = Math.max(maxLength, (right - left + 1));
            right++;
        }
        return maxLength;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        System.out.println("The input string is " + str);
 
        int len = longestUniqueSubsttr(str);
        System.out.println("The length of the longest "
                           + "non-repeating character "
                           + "substring is " + len);
    }
}

C#

// Include namespace system
using System;
 
public class GFG {
 
    public static int LongestUniqueSubsttr(string str)
    {
 
        // if string length is 0
        if (str.Length == 0)
            return 0;
 
        // if string length 1
        if (str.Length == 1)
            return 1;
 
        // if string length is more than 2
        int maxLength = 0;
        bool[] visited = new bool[256];
 
        // left and right pointer of sliding window
        int left = 0, right = 0;
        while (right < str.Length) {
 
            // if character is visited
            if (visited[str[right]]) {
 
                // The left pointer moves to the right
                // while marking visited characters as
                // false until the repeating character
                // is no longer part of the current
                // window.
                while (visited[str[right]]) {
 
                    visited[str[left]] = false;
                    left++;
                }
            }
 
            visited[str[right]] = true;
 
            // The length of the current window (right -
            // left + 1) is calculated and the answer is
            // updated accordingly.
            maxLength
                = Math.Max(maxLength, right - left + 1);
            right++;
        }
 
        return maxLength;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        var str = "geeksforgeeks";
        Console.WriteLine("The input string is " + str);
        var len = GFG.LongestUniqueSubsttr(str);
        Console.WriteLine("The length of the longest "
                          + "non-repeating character "
                          + "substring is "
                          + len.ToString());
    }
}

Javascript

function longestUniqueSubsttr(str) {
    // if string length is 0
    if (str.length === 0)
        return 0;
 
    // if string length 1
    if (str.length === 1)
        return 1;
 
    // if string length is more than 2
    let maxLength = 0;
    let visited = new Array(256).fill(false);
 
    // left and right pointer of sliding window
    let left = 0, right = 0;
    while (right < str.length) {
 
        // if character is visited
        if (visited[str.charCodeAt(right)]) {
 
            // The left pointer moves to the right while
            // marking visited characters as false until the
            // repeating character is no longer part of the
            // current window.
            while (visited[str.charCodeAt(right)]) {
                visited[str.charCodeAt(left)] = false;
                left++;
            }
        }
 
        visited[str.charCodeAt(right)] = true;
 
        // The length of the current window (right - left + 1)
        // is calculated and the answer is updated accordingly.
        maxLength = Math.max(maxLength, right - left + 1);
        right++;
    }
 
    return maxLength;
}
 
 
    let s = "geeksforgeeks";
    console.log("The input string is " + s);
    console.log("The length of the longest non-repeating "+
            "character substring is "+ longestUniqueSubsttr(s));   
      

Python3

import math
 
 
def longestUniqueSubsttr(s):
    # if string length is 0
    if len(s) == 0:
        return 0
 
    # if string length 1
    if len(s) == 1:
        return 1
 
    # if string length is more than 2
    maxLength = 0
    visited = [False] * 256
 
    # left and right pointer of sliding window
    left, right = 0, 0
    while right < len(s):
 
        # if character is visited
        if visited[ord(s[right])]:
 
            # The left pointer moves to the right while
            # marking visited characters as false until the
            # repeating character is no longer part of the
            # current window.
            while visited[ord(s[right])]:
 
                visited[ord(s[left])] = False
                left += 1
 
        visited[ord(s[right])] = True
 
        # The length of the current window (right - left + 1)
        # is calculated and the answer is updated accordingly.
        maxLength = max(maxLength, right - left + 1)
        right += 1
 
    return maxLength
 
 
# Driver Code
string = "geeksforgeeks"
print("The input string is", string)
length = longestUniqueSubsttr(string)
print("The length of the longest non-repeating character substring is", length)

Output

The input string is geeksforgeeks
The length of the longest non-repeating character substring is 7

Time Complexity: O(n), Since each character is processed by the left and right pointers exactly once.
Auxiliary Space: O(1)

Length of the longest substring without repeating characters by Storing the last index of each character:

The approach stores the last indexes of already visited characters. The idea is to traverse the string from left to right, for each character at index j, update the i pointer(starting index of current window) to be the maximum of its current value and last Index of str[j] + 1. This step ensures that i is moved to the appropriate position to exclude any repeating characters within the new window.

Below is the implementation of the above approach :

C++

// C++ program to find the length of the longest substring
// without repeating characters
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
 
int longestUniqueSubsttr(string str)
{
    int n = str.size();
 
    int res = 0; // result
 
    // last index of all characters is initialized
    // as -1
    vector<int> lastIndex(NO_OF_CHARS, -1);
 
    // Initialize start of current window
    int i = 0;
 
    // Move end of current window
    for (int j = 0; j < n; j++) {
 
        // Find the last index of str[j]
        // Update i (starting index of current window)
        // as maximum of current value of i and last
        // index plus 1
        i = max(i, lastIndex[str[j]] + 1);
 
        // Update result if we get a larger window
        res = max(res, j - i + 1);
 
        // Update last index of j.
        lastIndex[str[j]] = j;
    }
    return res;
}
 
// Driver code
int main()
{
    string str = "geeksforgeeks";
    cout << "The input string is " << str << endl;
    int len = longestUniqueSubsttr(str);
    cout << "The length of the longest non-repeating "
            "character substring is "
         << len;
    return 0;
}

Java

// Java program to find the length of the longest substring
// without repeating characters
import java.util.*;
 
public class GFG {
 
    static final int NO_OF_CHARS = 256;
 
    static int longestUniqueSubsttr(String str)
    {
        int n = str.length();
 
        int res = 0; // result
 
        // last index of all characters is initialized
        // as -1
        int[] lastIndex = new int[NO_OF_CHARS];
        Arrays.fill(lastIndex, -1);
 
        // Initialize start of current window
        int i = 0;
 
        // Move end of current window
        for (int j = 0; j < n; j++) {
 
            // Find the last index of str[j]
            // Update i (starting index of current window)
            // as maximum of current value of i and last
            // index plus 1
            i = Math.max(i, lastIndex[str.charAt(j)] + 1);
 
            // Update result if we get a larger window
            res = Math.max(res, j - i + 1);
 
            // Update last index of j.
            lastIndex[str.charAt(j)] = j;
        }
        return res;
    }
 
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        System.out.println("The input string is " + str);
        int len = longestUniqueSubsttr(str);
        System.out.println(
            "The length of "
            + "the longest non repeating character is "
            + len);
    }
}
// This code is contributed by Sumit Ghosh

C#

// C# program to find the length of the longest substring
// without repeating characters
using System;
public class GFG {
    static int NO_OF_CHARS = 256;
    static int longestUniqueSubsttr(string str)
    {
        int n = str.Length;
        int res = 0; // result
 
        // last index of all characters is initialized
        // as -1
        int[] lastIndex = new int[NO_OF_CHARS];
        Array.Fill(lastIndex, -1);
 
        // Initialize start of current window
        int i = 0;
 
        // Move end of current window
        for (int j = 0; j < n; j++) {
 
            // Find the last index of str[j]
            // Update i (starting index of current window)
            // as maximum of current value of i and last
            // index plus 1
            i = Math.Max(i, lastIndex[str[j]] + 1);
 
            // Update result if we get a larger window
            res = Math.Max(res, j - i + 1);
 
            // Update last index of j.
            lastIndex[str[j]] = j;
        }
        return res;
    }
 
    /* Driver program to test above function */
    static public void Main()
    {
        string str = "geeksforgeeks";
        Console.WriteLine("The input string is " + str);
        int len = longestUniqueSubsttr(str);
        Console.WriteLine(
            "The length of "
            + "the longest non repeating character is "
            + len);
    }
}
 
// This code is contributed by avanitrachhadiya2155

Javascript

// JavaScript program to find the length of the longest substring
// without repeating characters
var NO_OF_CHARS = 256;
 
function longestUniqueSubsttr(str)
    {
        var n = str.length;
 
        var res = 0; // result
 
        // last index of all characters is initialized
        // as -1
        let lastIndex = new Array(256).fill(-1);
 
        // Initialize start of current window
        var i = 0;
 
        // Move end of current window
        for (var j = 0; j < n; j++) {
 
            // Find the last index of str[j]
            // Update i (starting index of current window)
            // as maximum of current value of i and last
            // index plus 1
            i = Math.max(i, lastIndex[str.charAt(j)] + 1);
 
            // Update result if we get a larger window
            res = Math.max(res, j - i + 1);
 
            // Update last index of j.
            lastIndex[str.charAt(j)] = j;
        }
        return res;
    }
 
    /* Driver program to test above function */
     
        var str = "geeksforgeeks";
        console.log("The input string is " + str);
        var len = longestUniqueSubsttr(str);
        console.log("The length of the longest non repeating character is " + len);
 
// This code is contributed by shivanisinghss2110

Python3

# Python3 program to find the length
# of the longest substring
# without repeating characters
 
 
def longestUniqueSubsttr(string):
 
    # last index of every character
    last_idx = {}
    max_len = 0
 
    # starting index of current
    # window to calculate max_len
    start_idx = 0
 
    for i in range(0, len(string)):
 
        # Find the last index of str[i]
        # Update start_idx (starting index of current window)
        # as maximum of current value of start_idx and last
        # index plus 1
        if string[i] in last_idx:
            start_idx = max(start_idx, last_idx[string[i]] + 1)
 
        # Update result if we get a larger window
        max_len = max(max_len, i-start_idx + 1)
 
        # Update last index of current char.
        last_idx[string[i]] = i
 
    return max_len
 
 
# Driver program to test the above function
string = "geeksforgeeks"
print("The input string is " + string)
length = longestUniqueSubsttr(string)
print("The length of the longest non-repeating character" +
      " substring is " + str(length))

Output

The input string is geeksforgeeks
The length of the longest non-repeating character substring is 7

Time Complexity: O(n), each character is processed exactly twice: once when it enters the window (j) and once when it exits the window (i).
Auxiliary Space: O(1)

Suggest improvement

Maximum Product Subarray

Maximum Length Bitonic Subarray | Set 1 (O(n) time and O(n) space)

Share your thoughts in the comments

Length of the longest substring without repeating characters

Length of the longest substring without repeating characters using Sliding Window in O(n3) time:

C++

C

Java

C#

Javascript

Python3

Length of the longest substring without repeating characters using Sliding Window in O(n2) time:

C++

Java

C#

Javascript

Python3

Length of the longest substring without repeating characters using Binary Search on Answer:

C++

Java

C#

Javascript

Python3

Length of the longest substring without repeating characters using Sliding Window:

C++

Java

C#

Javascript

Python3

Length of the longest substring without repeating characters by Storing the last index of each character:

C++

Java

C#

Javascript

Python3

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?

Length of the longest substring without repeating characters using Sliding Window in O(n³) time:

Length of the longest substring without repeating characters using Sliding Window in O(n²) time: