Problem Statement: Given a String, find the length of longest substring without any repeating character.
Examples:
Example 1: Input: s = ”abcabcbb” Output: 3 Explanation: The answer is abc with length of 3. Example 2: Input: s = ”bbbbb” Output: 1 Explanation: The answer is b with length of 1 units.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Brute force Approach
Approach: This approach consists of taking the two loops one for traversing the string and another loop – nested loop for finding different substrings and after that, we will check for all substrings one by one and check for each and every element if the element is not found then we will store that element in HashSet otherwise we will break from the loop and count it.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int solve(string str) {
if(str.size()==0)
return 0;
int maxans = INT_MIN;
for (int i = 0; i < str.length(); i++) // outer loop for traversing the string
{
unordered_set < int > set;
for (int j = i; j < str.length(); j++) // nested loop for getting different string starting with str[i]
{
if (set.find(str[j]) != set.end()) // if element if found so mark it as ans and break from the loop
{
maxans = max(maxans, j - i);
break;
}
set.insert(str[j]);
}
}
return maxans;
}
int main() {
string str = "takeUforward";
cout << "The length of the longest substring without repeating characters is " <<
solve(str);
return 0;
}Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( N2 )
Space Complexity: O(N) where N is the size of HashSet taken for storing the elements
Java Code
import java.util.*;
public class Main {
static int solve(String str) {
if(str.length()==0)
return 0;
int maxans = Integer.MIN_VALUE;
for (int i = 0; i < str.length(); i++) // outer loop for traversing the string
{
Set < Character > se = new HashSet < > ();
for (int j = i; j < str.length(); j++) // nested loop for getting different
string starting with str[i]
{
if (se.contains(str.charAt(j))) // if element if found so mark it as ans
and break from the loop
{
maxans = Math.max(maxans, j - i);
break;
}
se.add(str.charAt(j));
}
}
return maxans;
}
public static void main(String args[]) {
String str = "takeUforward";
System.out.println("The length of the longest substring without repeating
characters is " + solve(str));
}
}Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( N2 )
Space Complexity: O(N) where N is the size of HashSet taken for storing the elements
Python Code
def solve(str: str) -> int:
if len(str) == 0:
return 0
maxans = -1
for i in range(len(str)): # outer loop for traversing the string
set = {}
# nested loop for getting different string starting with str[i]
for j in range(i, len(str)):
if str[j] in set: # if element if found so mark it as ans and break from the loop
maxans = max(maxans, j - i)
break
set[str[j]] = 1
return maxans
if __name__ == "__main__":
str = "takeUforward"
print("The length of the longest substring without repeating characters is", solve(str))Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( N2 )
Space Complexity: O(N) where N is the size of HashSet taken for storing the elements
Solution 2: Optimised Approach 1
Approach: We will have two pointers left and right. Pointer ‘left’ is used for maintaining the starting point of the substring while ‘right’ will maintain the endpoint of the substring.’ right’ pointer will move forward and check for the duplicate occurrence of the current element if found then the ‘left’ pointer will be shifted ahead so as to delete the duplicate elements.
Code:
C++ Code
#include <bits/stdc++.h>
#include<unordered_set>
using namespace std;
int solve(string str) {
if(str.size()==0)
return 0;
int maxans = INT_MIN;
unordered_set < int > set;
int l = 0;
for (int r = 0; r < str.length(); r++) // outer loop for traversing the string
{
if (set.find(str[r]) != set.end()) //if duplicate element is found
{
while (l < r && set.find(str[r]) != set.end()) {
set.erase(str[l]);
l++;
}
}
set.insert(str[r]);
maxans = max(maxans, r - l + 1);
}
return maxans;
}
int main() {
string str = "takeUforward";
cout << "The length of the longest substring without repeating characters is " <<
solve(str);
return 0;
}Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( 2*N ) (sometimes left and right both have to travel a complete array)
Space Complexity: O(N) where N is the size of HashSet taken for storing the elements
Java Code
import java.util.*;
public class Main {
static int solve(String str) {
if(str.length()==0)
return 0;
int maxans = Integer.MIN_VALUE;
Set < Character > set = new HashSet < > ();
int l = 0;
for (int r = 0; r < str.length(); r++) // outer loop for traversing the string
{
if (set.contains(str.charAt(r))) //if duplicate element is found
{
while (l < r && set.contains(str.charAt(r))) {
set.remove(str.charAt(l));
l++;
}
}
set.add(str.charAt(r));
maxans = Math.max(maxans, r - l + 1);
}
return maxans;
}
public static void main(String args[]) {
String str = "takeUforward";
System.out.println("The length of the longest substring without repeating
characters is " + solve(str));
}
}Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( 2*N ) (sometimes left and right both have to travel complete array)
Space Complexity: O(N) where N is the size of HashSet taken for storing the elements
Python Code
def solve(str: str) -> int:
if len(str) == 0:
return 0
maxans = float("-inf")
setx = set()
l = 0
for r in range(len(str)): # outer loop for traversing the string
if str[r] in setx: # if duplicate element is found
while l < r and str[r] in setx:
setx.remove(str[l])
l += 1
setx.add(str[r])
maxans = max(maxans, r - l + 1)
return maxans
if __name__ == "__main__":
str = "takeUforward"
print("The length of the longest substring without repeating characters is", solve(str))Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( 2*N ) (sometimes left and right both have to travel a complete array)
Space Complexity: O(N) where N is the size of HashSet taken for storing the elements
Solution 3: Optimised Approach 2
Approach: In this approach, we will make a map that will take care of counting the elements and maintaining the frequency of each and every element as a unity by taking the latest index of every element.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthofLongestSubstring(string s) {
vector < int > mpp(256, -1);
int left = 0, right = 0;
int n = s.size();
int len = 0;
while (right < n) {
if (mpp[s[right]] != -1)
left = max(mpp[s[right]] + 1, left);
mpp[s[right]] = right;
len = max(len, right - left + 1);
right++;
}
return len;
}
};
int main() {
string str = "takeUforward";
Solution obj;
cout << "The length of the longest substring without repeating characters is " << obj.lengthofLongestSubstring(str);
return 0;
}Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( N )
Space Complexity: O(N) where N represents the size of HashSet where we are storing our elements
Java Code
import java.util.*;
public class Main {
static int solve(String s) {
HashMap < Character, Integer > mpp = new HashMap < Character, Integer > ();
int left = 0, right = 0;
int n = s.length();
int len = 0;
while (right < n) {
if (mpp.containsKey(s.charAt(right))) left = Math.max(mpp.get(s.charAt(right)) + 1, left);
mpp.put(s.charAt(right), right);
len = Math.max(len, right - left + 1);
right++;
}
return len;
}
public static void main(String args[]) {
String str = "takeUforward";
System.out.println("The length of the longest substring without repeating
characters is " + solve(str));
}
}Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( N )
Space Complexity: O(N) where N represents the size of HashSet where we are storing our elements
Python Code
class Solution:
def lengthofLongestSubstring(self, s: str) -> int:
mpp = [-1] * 256
left = 0
right = 0
n = len(s)
length = 0
while right < n:
if mpp[ord(s[right])] != -1:
left = max(mpp[ord(s[right])] + 1, left)
mpp[ord(s[right])] = right
length = max(length, right - left + 1)
right += 1
return length
if __name__ == "__main__":
str = "takeUforward"
obj = Solution()
print("The length of the longest substring without repeating characters is",
obj.lengthofLongestSubstring(str))Output: The length of the longest substring without repeating characters is 9
Time Complexity: O( N )
Space Complexity: O(N) where N represents the size of HashSet where we are storing our elements
Special thanks to Gurmeet Singh and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article