Skip to content

Instantly share code, notes, and snippets.

@jutikorn
Created July 23, 2022 09:16
Show Gist options
  • Save jutikorn/effd598e18975e21d9994a921d0155a5 to your computer and use it in GitHub Desktop.
Save jutikorn/effd598e18975e21d9994a921d0155a5 to your computer and use it in GitHub Desktop.
Longest Substring with Same Letters after Replacement
import java.util.*;
class StringPermutation {
// obdbcaf
public static boolean findPermutation(String str, String pattern) {
int left = 0;
int patternLength = pattern.length();
HashMap<Character, Integer> map = new HashMap();
for(int i = 0; i < pattern.length(); i++){
int count = map.getOrDefault(pattern.charAt(i), 0) + 1;
map.put(pattern.charAt(i), count);
}
for(int right = 0; right < str.length(); right++){
char c = str.charAt(right);
if(map.containsKey(c)) {
int desc = map.getOrDefault(c, 0) -1;
map.put(c, desc);
patternLength--;
if(patternLength == 0) return true;
} else {
if(patternLength == 0) return true;
while(left < right) {
char previousC = str.charAt(left);
if(map.containsKey(previousC)) {
int inc = map.getOrDefault(previousC, 0) +1;
map.put(previousC, inc);
patternLength++;
}
left++;
}
}
}
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment