[Solution]Problem 71: Permutation in String [Microsoft]

Hashing, Strings, and a lot of love

Jan 13, 2023

If you like my writing, I would really appreciate an anonymous testimonial. You can drop it here.

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

Take the next step by subscribing here

I’m going to start with an announcement,

The newsletter giveaway has finished. Over 300 people will get this newsletter for free. To those that filled out the form, you will now have access to all the paid content in my newsletter, for the next year, no strings attached. This should help those of you struggling with the economic uncertainty of today. Use all the knowledge already shared that I will continue to share to boost your career.

Getting back to today’s question. How did you do on this question? Did you get the solution? Let me know by replying to this email.

This problem can be found as problem 567. Permutation in String

Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.

You can test your solution here

Step 1: Finding the Simple Edge Cases

In terms of wording and what it’s asking, this question is pretty straightforward. The tricky part is in the implementation. In such cases, one of the easiest first steps is to start discovering the algorithm is to simply start by attacking simple edge cases. This is a nice way to simplify your problem and discover some underlying hints about the structure of the problem. It allows you to hit upon the Communication and Problem-Solving pillars of cracking interviews in one easy sweep.

This is the 5 Pillar Approach that this newsletter uses to maximize your chances of success.

In our case, there is a clear edge case. Since we are checking for s1 being a part of s2, we know that we can return false if s1 is longer than s2.

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

This is a quick way to buy yourself some time and gain a few brownie points from the interviewer. So where do we go from here?

Here is where some previous knowledge can be helpful. Anytime we are looking for substrings(in our case s1) within a larger string (s2), the sliding window approach is one of your best friends. We’ve solved a lot of problems using that, so if you’re looking for practice with this approach, here are a few older posts on it.

Step 2: Sliding Window

The sliding window approach is pretty simple. Use two pointers to define an interval on a string/list, and check for your desired pattern/property in that interval. If you don’t find the pattern, move your window across to form a new interval.

This approach is great for a simple reason, it’s cheap. Sliding window problems can usually done in O(n) time. You will see this pattern pop up quite a bit, especially for questions involving anagrams or strings.

Our sliding window has one major simplification- the length of the window is fixed. We just need to slide our window across, comparing whether our values match. How do we do this?

The simplest approach would be to generate every permutation (anagram) of s1 and check whether the current window of s2 has them. This is extremely costly and presenting this as the final solution will get you kicked out of the interview (and most probably blacklisted from the company). Fortunately, there is a better approach, one that’s much easier to code and has lower complexity. It takes advantage of the sliding nature of the sliding window approach. What is it? Let’s get into it.

Step 3: An efficient comparison

To understand why the idea I’m going to show is better, let’s first understand why the idea of comparing permutations is bad. This comes down to something you should avoid at all costs, repeated work.

Take our current, brute-force approach. When you move on from one window to the next, you essentially discard everything you learned in the previous window and recreate all the permutations. This is completely unnecessary. Let’s say our window starts with the interval [0,4]. We find no matches, here so we go to the window [1,5]. Notice that most of our characters stay the same. When compared to our previous window, we only need to replace the character at [0] and add the char at [5]. This is the magic of the sliding window approach.

What does this mean? All we have to do is build the window once. After that, it’s just a matter of replacing the appropriate characters.

I can see the tube light going off in your mind. With this insight, you should be able to see 2 things-

Our windows will be stored hashmaps/dicts. We can leverage their O(1) time for lookup and insertion to quickly replace characters. Our sliding window character adjustments are made with the following 2 lines-
```
h2[s2[l]] -= 1
h2[s2[r]] = h2.get(s2[r], 0) + 1
```
Our comparison will just be checking if the two dicts are equal. High-level languages have this comparison feature built-in.

With that out of the way, the code should become relatively straightforward.

Step 4: Coding It Up

Here is the code for this solution.

from collections import Counter
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1)>len(s2): return False

        l, r = 0, len(s1)
        h1 = Counter(s1) 
        h2 = Counter(s2[:len(s1)])
        #Counter just returns the dict with the no. of occurences in a string

        while r < len(s2):
            if h1 == h2: return True
            h2[s2[l]] -= 1
            h2[s2[r]] = h2.get(s2[r], 0) + 1
            r += 1
            l += 1
        return h1 == h2

Time Complexity- O(len(s2) )

Space Complexity- O(len(s1))

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke,

Go kill all,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Technology Made Simple

Discussion about this post