Length of the longest substring without repeating characters
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 7Example 2:
Input: “w3wiki”
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(n3) 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++ 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 = "w3wiki";
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 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[] = "w3wiki";
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)
import java.util.HashMap;
public class LongestSubstring {
static int longestUniqueSubsttr(String str) {
int n = str.length();
int res = 0; // result
int i = 0;
// Creating a hash map to store the last positions of occurrence
HashMap<Character, Integer> lastIndex = new HashMap<>();
// Starting from the beginning of the string
for (int j = 0; j < n; j++) {
// If this character is seen before, then update i
if (lastIndex.containsKey(str.charAt(j))) {
i = Math.max(i, lastIndex.get(str.charAt(j)) + 1);
}
// Update result if needed
res = Math.max(res, j - i + 1);
// Update the last occurrence of the current character
lastIndex.put(str.charAt(j), j);
}
return res;
}
// Driver code
public static void main(String[] args) {
String str1 = "ABCDEFGABEF";
System.out.println("Length of the longest substring without repeating characters: " + longestUniqueSubsttr(str1));
String str2 = "w3wiki";
System.out.println("Length of the longest substring without repeating characters: " + longestUniqueSubsttr(str2));
}
}
# 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 = "w3wiki"
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
// 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 = "w3wiki";
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 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 = "w3wiki";
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.
Output
The input string is w3wiki 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(n2) 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++ 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 = "w3wiki";
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 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 = "w3wiki";
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
# 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 = "w3wiki"
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
// 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 = "w3wiki";
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 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 = "w3wiki";
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
Output
The input string is w3wiki 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:
#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 = "w3wiki";
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;
}
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 = "w3wiki";
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);
}
}
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 = "w3wiki"
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
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 = "w3wiki";
Console.WriteLine("The input string is " + str);
int len = LongestUniqueSubstring(str);
Console.WriteLine("The length of the longest non-repeating " +
"character substring is " + len);
}
}
// 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 = "w3wiki";
console.log("The input string is " + str);
const len = longestUniqueSubsttr(str);
console.log("The length of the longest non-repeating " +
"character substring is " + len);
Output
The input string is w3wiki 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. Theleft
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:
#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 = "w3wiki";
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;
}
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 = "w3wiki";
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);
}
}
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 = "w3wiki"
print("The input string is", string)
length = longestUniqueSubsttr(string)
print("The length of the longest non-repeating character substring is", length)
// 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 = "w3wiki";
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());
}
}
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 = "w3wiki";
console.log("The input string is " + s);
console.log("The length of the longest non-repeating "+
"character substring is "+ longestUniqueSubsttr(s));
Output
The input string is w3wiki 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 thei
pointer(starting index of current window)
to be the maximum of its current value andlast Index of
str[j] + 1
. This step ensures thati
is moved to the appropriate position to exclude any repeating characters within the new window.
Below is the implementation of the above approach :
// 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 = "w3wiki";
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 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 = "w3wiki";
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
# 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 = "w3wiki"
print("The input string is " + string)
length = longestUniqueSubsttr(string)
print("The length of the longest non-repeating character" +
" substring is " + str(length))
// 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 = "w3wiki";
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 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 = "w3wiki";
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
Output
The input string is w3wiki 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)
Contact Us