2023-02-04 Daily Challenge
Today I have done leetcode's February LeetCoding Challenge with cpp
.
February LeetCoding Challenge 4
Description
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
Constraints:
1 <= s1.length, s2.length <= 104
s1
ands2
consist of lowercase English letters.
Solution
auto speedup = [](){
cin.tie(nullptr);
cout.tie(nullptr);
ios::sync_with_stdio(false);
return 0;
}();
class Solution {
public:
bool checkInclusion(string p, string s) {
int sLen = s.length();
int pLen = p.length();
if(sLen < pLen) return false;
vector<int> target(26);
for(auto c : p) {
target[c - 'a'] += 1;
}
vector<int> current(26);
for(int i = 0; i < pLen; ++i) {
current[s[i] - 'a'] += 1;
}
vector<int> answer;
for(int i = pLen; i < sLen; ++i) {
if(current == target) return true;
current[s[i] - 'a'] += 1;
current[s[i - pLen] - 'a'] -= 1;
}
if(current == target) return true;
return false;
}
};
// Accepted
// 107/107 cases passed (6 ms)
// Your runtime beats 82.5 % of cpp submissions
// Your memory usage beats 32.35 % of cpp submissions (7.4 MB)