LeetCode-in-Java

3297. Count Substrings That Can Be Rearranged to Contain a String I

Medium

You are given two strings word1 and word2.

A string x is called valid if x can be rearranged to have word2 as a prefix.

Return the total number of valid substrings of word1.

Example 1:

Input: word1 = “bcca”, word2 = “abc”

Output: 1

Explanation:

The only valid substring is "bcca" which can be rearranged to "abcc" having "abc" as a prefix.

Example 2:

Input: word1 = “abcabc”, word2 = “abc”

Output: 10

Explanation:

All the substrings except substrings of size 1 and size 2 are valid.

Example 3:

Input: word1 = “abcabc”, word2 = “aaabc”

Output: 0

Constraints:

• 1 <= word1.length <= 105
• 1 <= word2.length <= 104
• word1 and word2 consist only of lowercase English letters.

Solution

public class Solution {
    public long validSubstringCount(String word1, String word2) {
        long res = 0;
        int keys = 0;
        int len = word1.length();
        int[] count = new int[26];
        boolean[] letters = new boolean[26];
        for (char letter : word2.toCharArray()) {
            int index = letter - 'a';
            if (count[index]++ == 0) {
                letters[index] = true;
                keys++;
            }
        }
        int start = 0;
        int end = 0;
        while (end < len) {
            int index = word1.charAt(end) - 'a';
            if (!letters[index]) {
                end++;
                continue;
            }
            if (--count[index] == 0) {
                --keys;
            }
            while (keys == 0) {
                res += len - end;
                int beginIndex = word1.charAt(start++) - 'a';
                if (!letters[beginIndex]) {
                    continue;
                }
                if (count[beginIndex]++ == 0) {
                    keys++;
                }
            }
            end++;
        }
        return res;
    }
}

This site is open source. Improve this page.