Given a string s, find the length of the longest substring without repeating characters.
For example –
Example 1:
Input: “abcabcbb” Output: 3
The output string is “abc”, with a length of 3.
Example 2:
Input: “bbbbb” Output: 1
The longest substring in this example is “b”. Its length is 1.
Example 3:
Input: “pwwkew” Output: 3
The answer is “wke”. Its length is 3.
In this tutorial, I am going to discuss how we can solve this problem efficiently using a sliding window approach and it’s java code. At the end of this tutorial, I have mentioned the link of the video tutorial.
Let’s first see the brute force approach to solve this problem. The simplest approach is to form all the possible substrings and track the length of the longest substring with unique characters.
The time complexity of this approach is O(n^3).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
//Brute force approach code public int lengthOfLongestSubstringBruteForce(String s) { int maxLen = 0; for(int i = 0; i < s.length(); i++) { for(int j = i+1; j <= s.length(); j++) { boolean isUnique = true; Set<Character> st = new HashSet<>(); for(int p = i; p < j; p++) { char ch = s.charAt(p); if(st.contains(ch)) { isUnique = false; break; } st.add(ch); } if(isUnique) { maxLen = Math.max(maxLen, j-i); } } } return maxLen; } |
Longest Substring Without Repeating Characters using Sliding Window – Java Code
Let’s improve our previous solution. In this example, I am going to explain how to find the length of longest non-repeating substring using sliding window approach.
The idea here is to maintain a window of unique character. Each window has start and end index, based on that we know the window size.To check unique character in a window, i am using set data structure. Set does not allow duplicate values and also the lookup time is O(1).
Here are the following steps to solve this problem –
- Declare two indexes i and j and initialize with zero. Variable i indicate index of the start window and j indicate end index.
- Traverse a string and pick one character at a time.
- First check, if a character exists in a set. If it doesn’t exist in a set then add them in a set and increment the count of j and the index of i remain as it is. Also, keep track of the length of a window.
- If character exists in a set then remove the character from a set and increment the count of i until all the characters in a window is unique again.
- Repeat this step until the string is traversed completely.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
Find first non-repeating character in a string
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/* Java code to find the length of longest substring without repeating characters. */ public class LongestSubstring { public static int lengthOfLongestSubstring(String s) { int maxCount = 0; int i = 0; int j = 0; int strLen = s.length(); //Declare set of characters Set<Character> st = new HashSet<>(); //Traverse a string while(i < strLen && j < strLen) { //If it's a unique character add in a set if(!st.contains(s.charAt(j))) { st.add(s.charAt(j)); j++; maxCount = Math.max(maxCount, j-i); } else { st.remove(s.charAt(i)); i++; } } return maxCount; } public static void main(String[] args) { String str = "abcdabcdbb"; int len = lengthOfLongestSubstring(str); System.out.println(" Length " + len); } } |
Longest Substring without Repeat InterviewBit Solution
The same problem is present in InterviewBit. The approach is same which i have already explained above.
Check if a String is subsequence of another string
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
//Longest substring without repeat interview public class Solution { public int lengthOfLongestSubstring(String A) { int result = 0; int start = 0; int end = 0; int strLen = A.length(); Set<Character> st = new HashSet<>(); while(start < strLen && end < strLen) { if(!st.contains(A.charAt(end))) { st.add(A.charAt(end++)); result = Math.max(result, end-start); } else { st.remove(A.charAt(start++)); } } return result; } } |
