HàPhan 河

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`.

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.

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".
``````

## Solution

Use same technique as Maxiumum sliding window

``````class Solution {
func findAnagrams(_ s: String, _ p: String) -> [Int] {
if s.count < p.count { return [] }

var searchTable = Array(repeating: 0, count: 26)

for c in p {
searchTable[c.val] += 1
}

var left = 0, right = 0, count = p.count
let arr = Array(s)
var res = [Int]()

while right < s.count {

let rightChar = arr[right]

if searchTable[rightChar.val] > 0 { count -= 1 } //found
if count == 0 { res.append(left) }

//decrease and move next
searchTable[rightChar.val] -= 1
right += 1

let leftChar = arr[left]

//to far
if right - left == p.count {
left += 1
if searchTable[leftChar.val] >= 0 { count += 1 }
searchTable[leftChar.val] += 1
}
}

return res
}
}

extension Character {
var val: Int {
return Int(self.asciiValue! - Character("a").asciiValue!)
}
}
``````