Skip to content

Instantly share code, notes, and snippets.

@amraks
Created June 5, 2018 00:47
Show Gist options
  • Save amraks/a66ef2a1c1543c693eec22e2d00dd6e9 to your computer and use it in GitHub Desktop.
Save amraks/a66ef2a1c1543c693eec22e2d00dd6e9 to your computer and use it in GitHub Desktop.
All anagrams indices of pattern in a string
package code;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
public static Map<Character, Integer> getCharacterFrequency(String s) {
Map<Character, Integer> m = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
if (m.containsKey(s.charAt(i))) {
m.put(s.charAt(i), m.get(s.charAt(i)) + 1);
} else {
m.put(s.charAt(i), 1);
}
}
return m;
}
public static List<Integer> getAnagramIndices(String s, String p) {
List<Integer> l = new ArrayList<>(); // result array
if (p.length() > s.length()) {
return l;
}
String current = "";
// create initial window
for (int i = 0; i < p.length(); i++) {
current = current.concat(String.valueOf(s.charAt(i)));
}
Map<Character, Integer> currentWindowMap = getCharacterFrequency(current); // sliding window map
Map<Character, Integer> patternMap = getCharacterFrequency(p); // input pattern map
int i = p.length();
do {
if (currentWindowMap.equals(patternMap)) {
l.add(i - p.length());
}
// character at beginning of sliding window
char c = s.charAt(i - p.length());
// reduce count of window's beginning character
currentWindowMap.put(c, currentWindowMap.get(c) - 1);
if (currentWindowMap.containsKey(c) && currentWindowMap.get(c) == 0) {
// remove char from map if it's count becomes 0
currentWindowMap.remove(c);
}
// slide the window
if (currentWindowMap.containsKey(s.charAt(i))) {
currentWindowMap.put(s.charAt(i), currentWindowMap.get(s.charAt(i)) + 1);
} else {
currentWindowMap.put(s.charAt(i), 1);
}
i += 1;
} while (i < s.length());
if (currentWindowMap.equals(patternMap)) {
l.add(i-p.length());
}
return l;
}
public static void main(String[] args) {
// eg. 1
System.out.println("eg. 1");
for (int i : getAnagramIndices("hello", "lol")) {
System.out.println(i);
}
;
System.out.println("eg. 2");
// eg. 2
for (int i : getAnagramIndices("msississsippi", "siss")) {
System.out.println(i);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment