Leetcode 75 Study Plan - Sliding Window/Two Pointer

[41071119H-Irene]

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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

[41071119H-Irene]

438. Answer

from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []

        p_count = Counter(p)
        s_count = Counter(s[:len(p)])
        #新增計數器
        #計算字串中字符出現頻率
        res = []
        for i in range(len(s) - len(p)):
            # for迴圈計數
            if p_count == s_count:
                res.append(i)

            # 滑動窗口右移一位，左邊的字符移除計數，右邊的字符增加計數
            s_count[s[i]] -= 1
            if s_count[s[i]] == 0:
                del s_count[s[i]]
            s_count[s[i+len(p)]] += 1

        if p_count == s_count:
            res.append(len(s) - len(p))

        return res

[41071119H-Irene]

424. Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achive this answer too.

[41071119H-Irene]

424. Answer

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        if len(s) == 0 or len(s) == 1:
            return len(s)
        kk = k
        i = max_count = 0
        counts = defaultdict(int)
        # 紀錄每個字元
        for char in s:
            counts[char] += 1
            if counts[char] > max_count:
                max_count = counts[char]
            else:
                kk -= 1
                #替換字元
            if kk < 0:
                counts[s[i]] -= 1
                i += 1
                kk += 1
        return max_count + k - kk

[41071119H-Irene]

小知識✨

Sliding Window/Two Pointer 兩個指標，讓範圍縮小