algoadvance

Leetcode 3083. Existence of a Substring in a String and Its Reverse

Problem Statement

Given two strings s1 and s2, check if any permutation of s1 exists as a substring in s2 or its reverse. Return true if such a permutation exists, otherwise return false.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length for s1 and s2?
    • Can s1 and s2 contain only lowercase/uppercase letters or any character?
  2. Edge Cases:
    • How should the function handle empty strings? For example, if either s1 or s2 is an empty string?
    • Are there performance considerations we need to take into account, like large inputs?

Assuming:

Strategy

  1. Permutation Check Using Frequency Count:
    • A permutation of s1 being a substring of s2 or its reverse hints that we need to check all substrings of s2 with the same length as s1.
  2. Sliding Window Approach:
    • Use a sliding window with the length of s1 to check all substrings in s2.
    • For each window, compare the frequency count of characters in the substring to the frequency count of characters in s1.
  3. Efficiency:
    • Instead of recalculating frequencies for each window from scratch, adjust the counts by sliding the window and updating counts accordingly.
  4. Reverse Check:
    • Concatenate s2 and its reversed version.
    • Apply the sliding window check to this concatenated string.

Code

#include <vector>
#include <string>
#include <algorithm>

bool checkInclusion(const std::string &s1, const std::string &s2) {
    if (s1.size() > s2.size()) {
        return false;
    }

    std::vector<int> s1Count(26, 0), s2Count(26, 0);
    int n1 = s1.size(), n2 = s2.size();

    // Count the frequency of characters in s1.
    for (char c : s1) {
        s1Count[c - 'a']++;
    }

    // Sliding window over s2
    for (int i = 0; i < n1; ++i) {
        s2Count[s2[i] - 'a']++;
    }

    if (s1Count == s2Count) {
        return true;
    }

    for (int i = n1; i < n2; ++i) {
        s2Count[s2[i] - 'a']++;
        s2Count[s2[i - n1] - 'a']--;

        if (s1Count == s2Count) {
            return true;
        }
    }
    
    // Check the reverse of s2
    std::string s2Rev = s2;
    std::reverse(s2Rev.begin(), s2Rev.end());
    std::fill(s2Count.begin(), s2Count.end(), 0);
    
    for (int i = 0; i < n1; ++i) {
        s2Count[s2Rev[i] - 'a']++;
    }

    if (s1Count == s2Count) {
        return true;
    }

    for (int i = n1; i < n2; ++i) {
        s2Count[s2Rev[i] - 'a']++;
        s2Count[s2Rev[i - n1] - 'a']--;

        if (s1Count == s2Count) {
            return true;
        }
    }
    
    return false;
}

Time Complexity

Conclusion

The function checkInclusion effectively checks for the existence of permutations of s1 in s2 or its reverse using a sliding window and frequency count approach, ensuring a time-efficient solution.

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