Given a string input of length n, find the length of the longest substring without repeating characters i.e return a substring that does not have any repeating characters.
Substring is the continuous sub-part of the string formed by removing zero or more characters from both ends.
The first and the only line consists of a string of length n containing lowercase alphabets.
You need to print the length of the longest unique characters substring.
1<= n <=10^5
Time Limit: 1 sec
abcabcbb
3
Substring "abc" has no repeating character with the length of 3.
aaaa
1
Think of creating all of the substrings.
O(N^3), where N is the length of the string.
We would be creating every substring, which takes N^2 time, and for checking whether it consists of unique characters, it will take N time.
O(N), where N is the length of the string.
Since we have used set for checking duplication in strings.
All tags
Sort by
Interview problems
java sol
public static int uniqueSubstrings(String input)
{
//write your code here
int n = input.length();
int len = 0, maxcnt = 0;
HashMap<Character, Integer> map = new HashMap<>();
for(int i =0;i<n;i++){
char ch = input.charAt(i);
if(map.containsKey(ch)) len = Math.max(len, map.get(ch)+1);
map.put(ch,i); //update characters last pos in the map;
maxcnt = Math.max(maxcnt, i-len+1);
}
return maxcnt;
}
Interview problems
Java solution using sliding window
public static int uniqueSubstrings(String input)
{
//write your code here
int n = input.length();
int l = 0;
int r = 0;
int maxCount = 0;
HashMap<Character,Integer> map = new HashMap<>();
while(r<n){
char ch = input.charAt(r);
if(!map.containsKey(ch)){
map.put(ch, map.getOrDefault(ch, 0)+1);
r++;
}else {
maxCount = Math.max(maxCount, map.size());
map.remove(input.charAt(l));
l++;
}
}
return maxCount==0 ? input.length() : maxCount;
}
Interview problems
Longest Substring Without Repeating Characters 🔁
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int lengthOfLongestSubstring(const string& input) {
// 📏 Variable to keep track of the maximum length of substring found
int maxlength = 0;
// 🔖 Variable to mark the starting index of the current substring
int start = 0;
// 🔁 Create a map to store the last index of each character
unordered_map<char, int> map;
// 🔁 Iterate through each character in the input string
for (int i = 0; i < input.length(); i++) {
// 🔍 If the character is found in the map, it means we have a duplicate
if (map.find(input[i]) != map.end()) {
// 📌 Update the start index to the next position after the last occurrence of the character
start = max(start, map[input[i]] + 1);
}
// 📝 Update the last index of the character in the map
map[input[i]] = i;
// 📏 Calculate the length of the current substring and update maxlength if it's greater
maxlength = max(maxlength, i - start + 1);
}
// 🔙 Return the maximum length of substring found
return maxlength;
}Interview problems
C++ solution::
#include <bits/stdc++.h>
int uniqueSubstrings(string input)
{
unordered_set<char> v;
int ans = 0, i=0, j=0;
while(j<input.size())
{
if(v.find(input[j])==v.end())
{
v.insert(input[j]);
j++;
}
else
{
ans = max(ans, (int)v.size());
v.erase(input[i]);
i++;
}
}
if(ans<(int)v.size()) return ans = v.size();
return ans;
}
Interview problems
Python O(n) solution using hash set()
def uniqueSubstrings(input ) :
n=len(input)
if n==0:
return 0
res=1
j=1
i=0
ans=set()
ans.add(input[0])
while(j<n):
if input[j] in ans:
res=max(res,j-i)
while (input[j] in ans):
ans.remove(input[i])
i+=1
ans.add(input[j])
else:
ans.add(input[j])
j+=1
res=max(res,j-i)
return resInterview problems
C++ | 2 Pointer ans Sliding Window Approach | T.C.-O(n)
#include <bits/stdc++.h>
int uniqueSubstrings(string input)
{
int n=input.size();
int l=0, r=0;
int maxLen=0;
int hash[256];
for(int i=0; i<256; i++)
hash[i]=-1;
while(r<n){
if(hash[input[r]]!=-1){
if(hash[input[r]]>=l){
l=hash[input[r]]+1;
}
}
maxLen=max(maxLen, r-l+1);
hash[input[r]]=r;
r++;
}
return maxLen;
}Interview problems
java | sliding window and two pointer approach
import java.util.* ;
import java.io.*;
public class Solution
{
public static int uniqueSubstrings(String input)
{
int right=0;
int left=0;
int window=0;
List<Character> ans=new ArrayList<>();
while(right < input.length()){
//we check if the element at pointer right have it if not then we add;
if(!ans.contains(input.charAt(right))){
ans.add(input.charAt(right));
right++;
window=Math.max(window, ans.size());
}
// we remove left element unit we finaaly remove the right element;
else{
ans.remove(Character.valueOf(input.charAt(left)));
left++;
}
}
return window;
}
}
Interview problems
In Java Solution
public static int uniqueSubstrings(String input)
{
HashMap<Character,Integer> hashMap = new HashMap<>();
int start =0;
int ans =0;
for(int i=0;i<input.length();i++){
char currChar = input.charAt(i);
if(hashMap.containsKey(currChar)){
start = Math.max(start,hashMap.get(currChar)+1);
}
hashMap.put(currChar, i);
ans = Math.max(ans, i-start+1);
}
return ans;
}
Interview problems
Easy Java Solution
import java.util.* ;
import java.io.*;
public class Solution
{
public static int uniqueSubstrings(String input)
{
int start = 0 , end = 0 , max = 0;
List<Character> ans = new ArrayList<>();
while(end < input.length()){
if(!ans.contains(input.charAt(end))){
ans.add(input.charAt(end));
end++;
max = Math.max(max,ans.size());
}
else{
ans.remove(Character.valueOf(input.charAt(start)));
start++;
}
}
return max;
}
}
Interview problems
python easy to understand optimal solution
from os import *
from sys import *
from collections import *
from math import *
def uniqueSubstrings(input) :
box=[] #list
n=len(input)
length=0
maxlength=float('-inf')
i=0
j=0
while j<n:
if input[j] in box:
box.pop(0)
#we pop starting ele from list to recheck
i+=1
length=length-1
# we move left pointer(i) by 1 stepe so #length should decrease by one
else:
box.append(input[j])
length=length+1
maxlength=max(maxlength,length)
j+=1
return maxlength
