source: https://leetcode.com/problems/permutation-in-string/
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Solution { public boolean checkInclusion(String s1, String s2) { int[] freq1 = new int[26]; char[] cArr = s1.toCharArray(); for(char c: cArr){ freq1[c-'a']++; } int l1 = s1.length(); int l2 = s2.length(); if(l1 > l2) return false; int[] freq2 = new int[26]; char[] arr = s2.toCharArray(); int lo = 0; for(int hi=0;hi<l2;hi++){ freq2[arr[hi]-'a']++; if((hi-lo)+1>l1){ freq2[arr[lo]-'a']--; lo++; } if((hi-lo)+1==l1){ if(compare(freq1, freq2)){ return true; } } } return false; } private boolean compare(int[] freq1, int[] freq2){ for(int i=0;i<26;i++){ if(freq1[i]!=freq2[i]){ return false; } } return true; } } |