Substring with Concatenation of All Words

hard

Acceptance: 36%

StringsSliding Window

A string and an array of equal-length words are given. Find every starting position in the string where a contiguous segment exactly matches some concatenation (in any order) of all the provided words. Each word must appear exactly as many times in the segment as it appears in the word list.

Examples

Example 1:

Input:s = "catdogcatdog", words = ["cat","dog"]

Output:[0,3,6]

Explanation: At index 0: 'catdog' is a valid concatenation. At index 3: 'dogcat' is valid. At index 6: 'catdog' is valid.

Example 2:

Input:s = "abcdef", words = ["ab","cd","ef"]

Output:[0]

Explanation: Only at index 0 does the substring 'abcdef' equal a valid concatenation of all three words.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Substring with Concatenation of All Words

Examples

Hints

Related Problems