algoadvance

Leetcode 567. Permutation in String

Problem Statement

Leetcode Problem 567: Permutation in String

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

Clarifying Questions

  1. Case Sensitivity: Should the comparison be case-sensitive?
    • Yes, it should be case-sensitive.
  2. Empty String Handling: What should be the output if either s1 or s2 is an empty string?
    • If s1 is empty, we can consider that an empty string is a permutation of any string, and we should return true. If s2 is empty, then no permutation of s1 can be found, thus we should return false.
  3. Character Set: Can we assume the strings contain only lowercase English letters?
    • Yes, the problem constraints normally imply that the strings contain only lowercase English letters.

Strategy

We’ll use the sliding window approach combined with a character frequency count to solve this problem efficiently.

  1. Frequency Count:
    • First, count the frequency of each character in s1.
  2. Sliding Window:
    • Use a sliding window of length equal to s1 on s2.
    • Check if the frequency of characters in the current window matches the frequency of characters in s1.
  3. Comparison:
    • If the frequencies match at any point, it means s2 contains a permutation of s1.

Code

#include <iostream>
#include <vector>

using namespace std;

bool matches(const vector<int>& s1_map, const vector<int>& s2_map) {
    for (int i = 0; i < 26; ++i) {
        if (s1_map[i] != s2_map[i]) {
            return false;
        }
    }
    return true;
}

bool checkInclusion(string s1, string s2) {
    if (s1.length() > s2.length()) return false;

    vector<int> s1_map(26, 0);
    vector<int> s2_map(26, 0);

    for (char c : s1) {
        s1_map[c - 'a']++;
    }

    int window_size = s1.length();

    for (int i = 0; i < s2.length(); ++i) {
        s2_map[s2[i] - 'a']++;
        
        if (i >= window_size) {
            s2_map[s2[i - window_size] - 'a']--;
        }

        if (i >= window_size - 1) {
            if (matches(s1_map, s2_map)) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    // Test cases
    cout << checkInclusion("ab", "eidbaooo") << endl; // Output: true
    cout << checkInclusion("ab", "eidboaoo") << endl; // Output: false
    return 0;
}

Time Complexity

This is efficient for the given problem constraints and ensures that we check all potential substrings in s2 while maintaining an optimal runtime.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI