251. Substring with Concatenation of All Words (Count)

Given a string s and an array words (all of equal length), return the number of starting indices in s of substrings that are a concatenation of every word in words exactly once, in any order, with no characters in between. Input: JSON {s, words}.

Input: JSON {s, words}.

Output: Integer — number of valid start indices.

Examples

Input: {"s":"barfoothefoobarman","words":["foo","bar"]}
Output: 2
Explanation: Indices 0 and 9.

Input: {"s":"wordgoodgoodgoodbestword","words":["word","good","best","word"]}
Output: 0
Explanation: No valid concatenation.

Input: {"s":"abab","words":["ab"]}
Output: 3
Explanation: Indices 0,1,2.

Constraints

• 1<=s.length<=10^4
• 1<=words.length<=5000
• all words same length

Asked by