Title:

Find All Anagrams

Specification:

Given a string s and a non-empty string p,
find all the start indices of p's anagrams in s.

Note:
Strings consists of lowercase English letters only,
and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.

Examples:

Example 1:

Input:
s: "cbaebabacd"     p: "abc"
Output:
[0, 6]

Example 2:

Input:
s: "abab"     p: "ab"
Output:
[0, 1, 2]

Initial Code and Signature:

``` import java.util.*; public interface AnagramMatcher { public List<Integer> findAnagrams(String s, String p); } ```

Algorithm:

Definition: An anagram of a string contains all the letters of the string.
However, the order of letters does not matter.

Main Idea:
Consider a sliding window over s.
The size of sliding window is the size of p.
Slide this window over s and check whether this window matches p.
If this window matches p, add the start of sliding window to the results.
Otherwise slide (i.e.; move) the window over s.

Steps:
1. Consider a sliding window of size p (p is the phrase to be found and matched).
This sliding window always contains p.length characters from s.
s is the string that is searched.)
This sliding window moves over s.
This sliding window initially starts at the beginning of s.
2. Read each letter in the slidingWindow and match it against the letters of p.
3. Is the letter found in p?
1. Yes: Eliminate that letter from phrase to be checked and go to the next letter in the sliding window.
2. No: Do another check:
1. Is the letter in p but eliminated previously?
Yes:
1. Find the position of the first occurrence of the letter in the slidingWindow.
2. Add all the letters between the start of the slidingWindow,
and that position to the phrase to be checked and matched again.
3. Move the beginning of the sliding window to immediately after that position.
4. Fill the sliding window with p.length characters.
5. Resume reading letters one by one and matching against the phrase.
Go to 2-.
No:
1. Move the beginning of the sliding window to the position right after the letter.
2. Fill the sliding window with p.length letters.
3. Reset the matching phrase to all the letters in p.
4. Resume reading letters one by one and matching against the phrase.
5. Go to 2-.
3. If the sliding window completely matches the phrase,
add the beginning of sliding window to the results.
4. Move the sliding Window one position to the right.
5. Resume Matching. Go to 2-.

Run-Time Analysis:

GitHub Project:

Code:

``` import java.util.*; /** * * @author Mahsa Sadi * * @since 2020 - 03 - 11 * * License: Creative Commons * * Copyright by Mahsa Sadi * */ public class AnagramMatcherV3 implements AnagramMatcher { /** * Problem: * * Find All Anagrams in a String * * * Description: * * Given a string s and a non-empty string p, * find all the start indices of p's anagrams in s. * * Note: * Strings consists of lower-case English letters only and the length of both strings s and p will not be larger than 20,100. * The order of output does not matter. * * * Solution: * * Definition: An anagram of a string contains all the letters of the string. * However, the order of letters does not matter. * * Main idea: * * Consider a sliding window over s. * The size of sliding window is the size of p. * Slide this window over s and check whether this window matches p. * If this window matches p, add the start of sliding window to the results. * Otherwise slide (i.e.; move) the window over s. * * * * 1- Consider a sliding window of size p ( p is the phrase to be found and matched). * This sliding window always contains p.length characters from s. * s is the string that is searched.) * This sliding window moves over s. * This sliding window initially starts at the beginning of s. * * * *2- Read each letter in the sliding window and match it against the letters of p. * * * *3- If the letter is found in p, * eliminate that letter from phrase to be checked and go to the next letter in the slidingWindow. * * *4- If the letter is not found in p do another check: * * *5- Check: Is the letter in p but eliminated previously? * * 5-1 Yes: * * 5-1-1: Find the position of the first occurrence of the letter in the sliding window. * * 5-1-2: Add all the letters between the start of the slidingWindow and that position to * the phrase to be checked and matched again. * 5-1-3: Move the beginning of the sliding window to immediately after that position. * 5-1-4: Fill the sliding window with p.length characters. * * 5-1-5: Resume reading letters one by one and matching against the phrase. * Go to 2-. * * 5-2: No: * 5-1: Move the beginning of the sliding window to the position right after the letter. * 5-2: Fill the sliding window with p.length letters. * 5-3: reset the matching phrase to all the letters in p. * 5-4: Resume reading letters one by one and matching against the phrase. * Go to 2-. * * * * 6- If the sliding window completely matches the phrase, * add the beginning of sliding window to the results. * * 7- Move the sliding Window one position to the right. * * 8- Resume Matching. Go to 2-. * * */ @Override public List<Integer> findAnagrams(String s, String p) { List indices = new ArrayList (); int startOfSlidingWindow, endOfSlidingWindow, currentPositionInSlidingWindow; startOfSlidingWindow = currentPositionInSlidingWindow = 0; int slidingWindowLength = p.length(); endOfSlidingWindow = slidingWindowLength - 1; StringBuilder expected = new StringBuilder (p); while (endOfSlidingWindow < s.length()) { while (currentPositionInSlidingWindow <= endOfSlidingWindow && endOfSlidingWindow < s.length ()) { char ch = s.charAt(currentPositionInSlidingWindow); boolean charIsInP = false; for (int i = 0; i < expected.length(); i++ ) { if (ch == expected.charAt(i)) { charIsInP = true; expected.deleteCharAt(i); break; } } if (charIsInP) currentPositionInSlidingWindow++; else if (!charIsInP) { boolean charWasInPAndEliminatedBefore = false; for (int i = startOfSlidingWindow; i < currentPositionInSlidingWindow; i++) if (s.charAt(i) == s.charAt(currentPositionInSlidingWindow)) { for (int j = startOfSlidingWindow; j < i; j++) expected.append(s.charAt(j)); endOfSlidingWindow = endOfSlidingWindow + ( i - startOfSlidingWindow + 1 ); startOfSlidingWindow = i + 1; currentPositionInSlidingWindow ++; charWasInPAndEliminatedBefore = true; break; } if (!charWasInPAndEliminatedBefore) { startOfSlidingWindow = currentPositionInSlidingWindow + 1; endOfSlidingWindow = startOfSlidingWindow + slidingWindowLength - 1; currentPositionInSlidingWindow = startOfSlidingWindow; expected = new StringBuilder (p); } } } if (endOfSlidingWindow >= s.length()) break; else if (expected.length() == 0 ) { indices.add(startOfSlidingWindow); expected.append(s.charAt(startOfSlidingWindow)); startOfSlidingWindow++; endOfSlidingWindow++; currentPositionInSlidingWindow = endOfSlidingWindow; } } return indices; } } ```