Solve Top LeetCode Problem Smartly
In now days, everyone is practicing DS & Algo problem using Leetcode,HackerRank or anyother platform. One common thing I felt If we understand the pattern of problem, we can reuse the same pattern to solve other problems with slight changes in our logic. I have listed out some problems related to finding the Longest (sub-string/sub-sequence/sub-array).
- Longest Substring with K unique characters
- Longest Substring without non repeating character
- Longest common substring
- Longest common sub sequence
- Longest repeating sub sequence
- Longest palindromic sub sequence
We can divide above problems into 2 pattern :
- Sliding Window
- Dynamic Programming
Sliding window pattern :
Longest Substring With K Unique Characters
Longest Substring Without Non Repeating Character
___________________________________________________________________
Dynamic Programming :
Longest common substring
Longest common sub sequence
Longest repeating sub sequence
Longest palindromic sub sequence
Let’s start with Sliding window pattern. There is common pattern when ever we apply sliding window. Sliding window is combination of of two pointers and hash map or hash table.
// Pointers int i = 0;
int j = 0;// Map Map<Character, Integer> map = new HashMap<>();
For each sliding window problem we need to take care of window size,it can be fixed or variable, which can be calculated as
int windowSize = j-i+1;Now, we need to run a while loop and keep comparing the window size with map size with (>,==,<).
while (j < string.length()){
if(map.size() > windowSize){
// some logic
}
if(map.size() == windowSize){
// some logic
}
if(map.size() < windowSize){
// some logic
}If we combine above things , we can write sliding window base code :
1. Pointers Intialization
int i = 0;
int j = 0;2. Map Intialization Map<Character, Integer> map = new HashMap<>();3. Initialising result int maxLength = Integer.MIN_VALUE;4. Run While loop, till j reaches to end of stringwhile (j < string.length()){ 4.1. Update character frequency in map map.put(string.charAt(j),map.getOrDefault(string.charAt(j),0)+1);
4.2. Update window size
int windowSize = j-i+1; 4.3. If map size is less than current window size, keep moving the j pointer to right if(map.size() < windowSize){
j++;
} 4.4. If map size is equal to current window size, find out max length and move j pointer to right if(map.size() == windowSize){
maxLength = Math.max(maxLength,j-i+1);
j++;
}4.5. If map size is greater than current window size, run while loop till map size is greater than window size, and update the map by decreasing the character frequency with moving the i pointer to right. When frequency count becomes zero, remove that character from map. if(map.size() > windowSize){
while (map.size() > windowSize){
map.put(string.charAt(i),map.get(string.charAt(i))-1);
if(map.get(string.charAt(i)) == 0){
map.remove(string.charAt(i));
}
i++;
}
j++;
}
}
This base code is can be reused everywhere, let us start one by one.
- Longest Substring with K unique characters
Here, just we need to replace our window size with K. Basically it is Fixed window problem. In problem it has stated that, window size will always be K.
so by replacing int windowSize = j-i+1 to K, we can write code like below :
package SlidingWindow;
import java.util.HashMap;
import java.util.Map;
/**
* @author Vipul Pachauri
*/
public class LongestSubstringWithKUniqueCharacters {
public static void main(String[] args) {
String string = "aabbccaadddddbbbaaaa";
int K = 3;
solve(string,K);
}
private static void solve(String string,int k) {
int i =0;
int j=0;
Map<Character, Integer> map = new HashMap<>();
int maxLength = Integer.MIN_VALUE;
while (j < string.length()){
map.put(string.charAt(j),map.getOrDefault(string.charAt(j),0)+1);
if(map.size() < K){
j++;
}
if(map.size() == K){
maxLength = Math.max(maxLength,j-i+1);
j++;
}
if(map.size() > K){
while (map.size() > K){
map.put(string.charAt(i),map.get(string.charAt(i))-1);
if(map.get(string.charAt(i)) == 0){
map.remove(string.charAt(i));
}
i++;
}
j++;
}
}
System.out.println(maxLength);
}
}And you are done my friend.
2. Longest Substring without non repeating character
This problem says, non repeating means all characters are unique. Right!! So we can say, It is similar to our previous problem, where we had K unique characters and here we have all unique characters.
Now, K is replaced with window size, which makes is variable sliding window problem.
package SlidingWindow;
import java.util.HashMap;
import java.util.Map;
/**
* @author Vipul Pachauri
*/
public class LongestSubstringWithoutNonRepeatingCharacter {
public static void main(String[] args) {
String string = "abcabcbbbb";
solve(string);
}
private static void solve(String string) {
int i = 0;
int j = 0;
Map<Character, Integer> map = new HashMap<>();
int maxLength = Integer.MIN_VALUE;
while (j < string.length()){
map.put(string.charAt(j),map.getOrDefault(string.charAt(j),0)+1);
// Replace K with (j-i+1)
int windowSize = j-i+1;
if(map.size() > windowSize){
j++;
}
if(map.size() == windowSize){
maxLength = Math.max(maxLength,j-i+1);
j++;
}
if(map.size() < windowSize){
while (map.size() < windowSize){
map.put(string.charAt(i),map.get(string.charAt(i))-1);
if(map.get(string.charAt(i)) == 0){
map.remove(string.charAt(i));
}
i++;
windowSize = j-i+1;
}
j++;
}
}
System.out.println(maxLength);
}
}And again you are done my friend. Happy face !!
But, here you can see in comparing window size with map size , we have replaced < with >, think about it and let me know in comments.
See you in my next blog. Happy Learning !!