May Leetcode Challenge

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!)
    }
}

May Leetcode Challenge - Day 17

Solution

Comments