_567. Permutation in String.md

567. Permutation in String

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 05, 2024

Last updated : July 05, 2024

---

Related Topics : Hash Table, Two Pointers, String, Sliding Window

Acceptance Rate : 44.535 %

---

Version 1

In version 1, I just went with a straightforward counter approach. Since Python Counter objects have a built-in comparing method, I decided to simply use that. It's still technically $O(n)$ in total since the counter size will be at most 26 (since it's only counting) letters, but it's still less than ideal.

Version 2

In version 2, I swapped over to, while still using a counter, only committing a comparison for the values that are being updated. That is, the values at the front of the window being added and the values are the end of the window that are being dropped. We have to find a case where all values line up, so we iterate initially for the first len(s1) letters then proceed with only incremental updates from that point onwards.

Fun Testcase

When creating version 2, I encountered a rather fun test case:

s1 = "trinitrophenylmethylnitramine"
s2 = "dinitrophenylhydrazinetrinitrophenylmethylnitramine"

Clearly, s1 matches the ending of s2 exactly, but my original code for version 2 (the incomplete v2) was resulting in False. Eventually, I realized that the cause was that during addings and subtractions of the same letter, it would cause match to increment by 2 due to the the "new values" equallying the expected values in s1's counter. This would only happen when the values where originally the correct value when it occured.

I added the if cL == cR : continue check and that was resolved quickly (as a if the previous wasn't a solution and didn't return, then this clearly wouldn't be a solution either since it's equal in the letter counts).

---

Solutions

• m567 v1 Counter Equivalence.py
• m567 v2 Running Counter.py

Python

m567 v1 Counter Equivalence.py

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        cnt1 = Counter(s1)
        cnt2 = Counter(s2[:len(s1) - 1])

        for cL, cR in zip(s2, s2[len(s1) - 1 : len(s2)]) :
            cnt2[cR] += 1
            if cnt1 == cnt2 :
                return True
            cnt2[cL] -= 1

        return False

m567 v2 Running Counter.py

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        cnt1 = [0] * 26
        cnt2 = [0] * 26

        if len(s1) > len(s2) :
            return False

        for c1, c2 in zip(s1, s2) :
            cnt1[ord(c1) - ord('a')] += 1
            cnt2[ord(c2) - ord('a')] += 1

        matches = [cnt1[x] == cnt2[x] for x in range(len(cnt1))].count(True)

        if matches == 26 :
            return True
        for cL, cR in zip(s2, s2[len(s1):]) :
            cnt2[ord(cL) - ord('a')] -= 1
            cnt2[ord(cR) - ord('a')] += 1

            if cL == cR :
                continue

            if cnt2[ord(cR) - ord('a')] == cnt1[ord(cR) - ord('a')] :
                matches += 1
            elif cnt2[ord(cR) - ord('a')] == cnt1[ord(cR) - ord('a')] + 1 :
                matches -= 1

            if cnt2[ord(cL) - ord('a')] == cnt1[ord(cL) - ord('a')] :
                matches += 1
            elif cnt2[ord(cL) - ord('a')] == cnt1[ord(cL) - ord('a')] - 1 :
                matches -= 1

            if matches == 26 :
                return True

        return False