2021-12-18: find all letter ectopic words in the string. Given two characters

2021-12-18： Find all alphabetic words in the string .

Given two strings s and p, find s All in p Of Heterotopic words The string of , Returns the starting index of these substrings . Regardless of the order of the answer output .

Heterotopic words A string formed by rearrangement of the same letters （ Include the same string ）.

Power button 438.

answer 2021-12-18：

The sliding window . Balance sheet .

Time complexity ：O(N).

Spatial complexity ：O(1).

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    s := "abab"
    p := "ab"
    ret := findAnagrams(s, p)
    fmt.Println(ret)
}

func findAnagrams(s, p string) []int {
    ans := make([]int, 0)
    if len(s) < len(p) {
        return ans
    }
    str := []byte(s)
    N := len(str)
    pst := []byte(p)
    M := len(pst)
    map0 := make(map[byte]int)
    for _, cha := range pst {
        map0[cha]++
    }
    all := M
    for end := 0; end < M-1; end++ {
        if _, ok := map0[str[end]]; ok {
            count := map0[str[end]]
            if count > 0 {
                all--
            }
            map0[str[end]] = count - 1
        }
    }
    for end, start := M-1, 0; end < N; end, start = end+1, start+1 {
        if _, ok := map0[str[end]]; ok {
            count := map0[str[end]]
            if count > 0 {
                all--
            }
            map0[str[end]] = count - 1
        }
        if all == 0 {
            ans = append(ans, start)
        }
        if _, ok := map0[str[start]]; ok {
            count := map0[str[start]]
            if count >= 0 {
                all++
            }
            map0[str[start]] = count + 1
        }
    }
    return ans
}

The results are as follows ：

picture

Zuo Shen java Code