Write a code to find all Anagrams in a String. Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Both the strings only consist of lowercase English letters. The length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input: s: “cbaebabacd” p: “abc”
Output: [0, 6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:
Input: s: “abab” p: “ab”
Output: [0, 1, 2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.
What is Anagram?
Two strings are said to be anagrams of each other, if it contains the same character only the order of characters in both strings is different.
For example – The strings car and rac are anagrams of each other.
This problem is the toughest version of check whether two strings are anagrams of each other.
Find All Anagrams in a String – Java Code
In this example, I’ll discuss the approach using a map and a sliding window. The sliding window size will be equal to the length of the string p. Instead of using HashMap here, we are going to use an array of fixed sizes (26).
As in the problem statement, it is already mentioned that both the string consists of lowercase English letters.
The time complexity of this approach is O(n). Its space complexity is O(1), as we are using a fixed-size array that doesn’t depend on the input length.
Find All Anagrams in a String Video Tutorial
|
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
//Find All Anagrams using Fixed Size Array and Sliding Window public class AllAnagrams { public static List<Integer> findAnagrams(String s, String p) { List<Integer> result = new ArrayList<>(); //Length of string p and s int pLen = p.length(); int sLen = s.length(); // Return empty result if any of the condition is true. if (s == null || s.length() == 0 || sLen < pLen) { return result; } //Declare an array of fixed sized. int[] pArr = new int[26]; int[] sArr = new int[26]; /* Put character count of array p in pArr. * Also, Create first window of size pLen. */ for (int i = 0; i < p.length(); i++) { pArr[p.charAt(i) - 'a']++; sArr[s.charAt(i) - 'a']++; } for (int i = 0; i < sLen - pLen; i++) { if (isAnagram(pArr, sArr)) { result.add(i); } sArr[s.charAt(i) - 'a']--; sArr[s.charAt(i+pLen) - 'a']++; } if (isAnagram(pArr, sArr)) { result.add(sLen - pLen); } return result; } public static boolean isAnagram(int[] pArr, int[] sArr) { for (int i = 0; i < pArr.length; i++) { if (pArr[i] != sArr[i]) { return false; } } return true; } public static void main(String[] args) { String s = "cbaebabacd"; String p = "abc"; List<Integer> result = findAnagrams(s, p); for(Integer value : result) { System.out.print(value + " "); } } } |
Data Structure Video Tutorials
Programming Questions on Arrays
