Back to DSA
Permutation in String
mediumTwo strings are provided. Determine whether the second string contains any substring that is a rearrangement (permutation) of the first string. Return true if such a substring exists, false otherwise.
Examples
Example 1:
Input:
pattern = "xy", text = "axyzbxyx"Output:
trueExplanation: The substring 'xy' starting at index 1 is itself a permutation of 'xy'.
Example 2:
Input:
pattern = "ab", text = "acbddd"Output:
falseExplanation: No contiguous substring of length 2 in the text is a rearrangement of 'ab'.
Hints
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] s1Count = new int[26], s2Count = new int[26];
for (int i = 0; i < s1.length(); i++) {
s1Count[s1.charAt(i) - 'a']++;
s2Count[s2.charAt(i) - 'a']++;
}
for (int i = 0; i < s2.length() - s1.length(); i++) {
if (java.util.Arrays.equals(s1Count, s2Count)) return true;
s2Count[s2.charAt(i + s1.length()) - 'a']++;
s2Count[s2.charAt(i) - 'a']--;
}
return java.util.Arrays.equals(s1Count, s2Count);
}
}Time complexity
O(n)Space complexity
O(1)