LeetCode - CheckInclusion  

by ne on 2022-08-27 under Algo/DS/Problems tagged with leetcode

The problem belongs to LeetCode, here is the link to the problem

Following code segment contains the description in the class comments, followed by fully working solution

 

 


/**
 * 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").
 */
public class CheckInclusion {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        char[] s1Arr = s1.toCharArray();
        char[] s2Arr = s2.toCharArray();
        int[] buck1 = new int[256];
        int[] buck2 = new int[256];
        for (char c : s1Arr) {
            buck1[c]++;
        }
        for (int j = 0; j < s1Arr.length - 1; j++) {
            buck2[s2Arr[j]]++;
        }
        for (int i = 0; i < 1 + s2Arr.length - s1Arr.length; i++) {
            boolean match = true;
            buck2[s2Arr[i + s1Arr.length - 1]]++;
            for (char c : s1Arr) {
                if (buck1[c] != buck2[c]) {
                    match = false;
                    break;
                }
            }
            if (match) return true;
            buck2[s2Arr[i]]--;
        }
        return false;
    }
}