Sliding WindowHardO(n × w) time · O(m × w) space

Words Concatenation

Ramayana — Valmiki's Saptakanda — Finding All Windows Where Sacred Word-Groups Are Concatenated

पदानां समूहः यत्र क्रमेण संनिहितः। तत् स्थानं पावनं ज्ञेयं — खोजयेत् सर्वदा॥

*Where all the sacred words appear consecutively in some order — that place is holy. Seek it always.*

The Story

Valmiki's seven Kandas of the Ramayana each began with a sacred invocation. The Saptakanda key was a set of words `["ram", "sita", "jay"]` — three words of equal length, each appearing exactly once. The sage believed these three words, in ANY order, concatenated one after another, formed a sacred invocation. He needed to find every starting position in the grand scroll `s` where such a concatenation occurred.

"The challenge," Valmiki told his disciple Bharadvaja, "is that the words can appear in any permutation. `'ramsitajay'`, `'jayramsite'`, `'sitaramjay'` — all equally sacred. But they must be contiguous and cover exactly the right number of characters."

"Total window length = number of words × length of each word = 3 × 3 = 9."

"If I check every window of length 9... there could be millions of positions in a long scroll," Bharadvaja said. "And checking each window requires extracting words and comparing frequencies."

"The key insight," Valmiki said, "is that all words have the same length `w`. So the scroll can be read as a sequence of w-length chunks. And within those chunks, we have a sliding window of exactly `m` words (m = number of words)."

"But the starting position matters — we can start reading chunks at offset 0, 1, 2, ... w-1. So we run w separate sliding-window passes, one for each starting offset."

Valmiki demonstrated with `s = "barfoothefoobarman"`, `words = ["foo", "bar"]`: - w = 3 (each word length), m = 2 (number of words), totalLen = 6 - need = {"foo":1, "bar":1}

**Pass for offset 0** (reading at positions 0, 3, 6, 9, 12, 15...): - Words at positions: `"bar"(0)`, `"foo"(3)`, `"the"(6)`, `"foo"(9)`, `"bar"(12)`, `"man"(15)` - Sliding window of 2 words: - ["bar","foo"]: seen={"bar":1,"foo":1}. matches need! Add index 0. ✓ - Slide: remove "bar", add "the": seen={"foo":1,"the":1}. "the" not in need → RESET window - ["foo","bar"]: seen={"foo":1,"bar":1}. matches! Add index 9. ✓ - Slide: remove "foo", add "man": "man" not in need → RESET

**Pass for offset 1** (positions 1, 4, 7, ...): no valid windows found **Pass for offset 2** (positions 2, 5, 8, ...): no valid windows found

Result: [0, 9] ✓

"The reset optimization is crucial," Valmiki explained. "When we encounter a word NOT in `need` — like `"the"` — none of the windows crossing this word can be valid. We reset the entire sliding window: clear `seen`, reset `count=0`, set `left` to the next position after the invalid word."

"What about valid words that appear too many times?" Bharadvaja asked. "Like `words=["foo","foo"]` and we see three `"foo"` in a row?"

"When `seen[word] > need[word]`, we have an excess. Shrink from the left: remove words one at a time until `seen[word] == need[word]` again. This is the same shrink logic as regular sliding window."

Bharadwaja found all invocation positions in the Ramayana scroll. The sacred concatenations were identified, marked, and celebrated.

"This is the hardest sliding window variant," Valmiki said, "because the 'elements' are words, not characters, and we must handle three cases per new word: not in need (reset), excess (shrink), and perfect (possibly record if count==m)."

This is the word-level Sliding Window for finding all concatenated word substrings.

Bharadvaja's First Instinct

For every starting index, extract m consecutive words of length w. Build frequency map and compare with need. O(n × m × w) time.

java

public List<Integer> findSubstringBruteForce(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    int wLen = words[0].length();
    int m = words.length;
    int totalLen = m * wLen;
    
    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.merge(w, 1, Integer::sum);
    
    for (int i = 0; i <= s.length() - totalLen; i++) {
        Map<String, Integer> seen = new HashMap<>();
        int j = 0;
        while (j < m) {
            String word = s.substring(i + j * wLen, i + (j + 1) * wLen);
            if (!need.containsKey(word)) break;
            seen.merge(word, 1, Integer::sum);
            if (seen.get(word) > need.get(word)) break;
            j++;
        }
        if (j == m) result.add(i);
    }
    return result;
}

Valmiki's Wisdom

Run w separate sliding windows (one per starting offset 0..w-1). Each pass reads the string as word-chunks. For each new word: - Not in need → RESET window - In need but excess (seen>need) → SHRINK from left - In need and fine → expand; if count==m → record start, shrink left This gives O(n) per pass × w passes = O(n×w) total.

java

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    if (s.isEmpty() || words.length == 0) return result;
    
    int wLen = words[0].length();
    int m = words.length;
    int n = s.length();
    
    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.merge(w, 1, Integer::sum);
    
    // Run one pass per starting offset (0 to wLen-1)
    for (int start = 0; start < wLen; start++) {
        Map<String, Integer> seen = new HashMap<>();
        int count = 0;    // Words correctly in window
        int left = start; // Left boundary of word-window
        
        for (int right = start; right + wLen <= n; right += wLen) {
            String word = s.substring(right, right + wLen);
            
            if (!need.containsKey(word)) {
                // Invalid word: reset window
                seen.clear();
                count = 0;
                left = right + wLen;
            } else {
                seen.merge(word, 1, Integer::sum);
                count++;
                
                // Too many of this word: shrink from left
                while (seen.get(word) > need.get(word)) {
                    String leftWord = s.substring(left, left + wLen);
                    seen.merge(leftWord, -1, Integer::sum);
                    count--;
                    left += wLen;
                }
                
                // Valid window of exactly m words
                if (count == m) {
                    result.add(left);
                    // Slide: remove leftmost word
                    String leftWord = s.substring(left, left + wLen);
                    seen.merge(leftWord, -1, Integer::sum);
                    count--;
                    left += wLen;
                }
            }
        }
    }
    return result;
}

// Test
public static void main(String[] args) {
    System.out.println(new Solution().findSubstring("barfoothefoobarman", new String[]{"foo","bar"})); // [0, 9]
    System.out.println(new Solution().findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","word"})); // []
}

Step-by-Step Walkthrough

s="wordgoodgoodgoodbestword", words=["word","good","best","good"]
w=4, m=4, need={word:1, good:2, best:1}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Offset 0 pass (positions 0,4,8,12,16,20):
words: word(0), good(4), good(8), good(12), best(16), word(20)

right=0 "word": seen={word:1}, count=1
right=4 "good": seen={word:1,good:1}, count=2
right=8 "good": seen={good:2}, count=3
right=12 "good": seen[good]=3 > need[good]=2!
  Shrink: remove left=0 "word": seen={good:3}, count=2. left=4.
  seen[good]=3 still > 2!
  Shrink: remove left=4 "good": seen={good:2}, count=1. left=8.
  seen[good]=2 == 2. Stop shrink.
  count=1 ≠ m
right=16 "best": seen={good:2,best:1}, count=2
right=20 "word": seen={good:2,best:1,word:1}, count=3 ≠ m=4

No result for offset 0.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return []  (no valid concatenation exists)

Deep Insight

**Why run w separate passes?** All words have the same length w. A valid window starts at index i where `i % w` aligns with one of the w offsets. By grouping positions 0, w, 2w... into one pass; 1, w+1, 2w+1... into another; etc., we ensure every valid start position is covered without redundancy.

**Three word-states in the sliding window:** 1. **Not in need**: Full reset — nothing after this point can extend the current window 2. **In need, excess**: Shrink from left — remove words one at a time 3. **In need, normal**: Count up; if count==m, we have a valid window (record and slide)

**Why not just use the O(n×m) brute force?** For long strings with many words, the brute force is O(n × m × w). The sliding window is O(n × w / w × w) = O(n × w), which is better when m is large.

**Edge cases:** - Duplicate words in `words` array: need[word] > 1; the window must contain exactly that many - Single word: m=1, trivial fixed-window match - s shorter than totalLen: empty result

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n × m × w)	O(m × w)	n positions × m-word check × w chars per word
Optimal	O(n × w)	O(m × w)	w passes × O(n/w) word-steps each; seen map holds m entries of w-length words

Pattern Recognition

✅ Fixed total window length (m words × w chars)
✅ Words of equal length — can be processed at word-level
✅ w separate sliding window passes (one per offset)
✅ Three-state word handling: reset/shrink/count

**LeetCode Trigger Phrases:**
→ "substring with concatenation of all words"
→ "all words... every word exactly once"
→ "words of equal length" + find all start indices

Bhagavad Gita 18.66

सर्वधर्मान्परित्यज्य मामेकं शरणं व्रज। अहं त्वा सर्वपापेभ्यो मोक्षयिष्यामि मा शुचः॥

Abandon all varieties of dharma and simply surrender unto Me alone. I shall liberate you from all sinful reactions; do not fear.

Connection: The algorithm seeks positions where ALL required words appear together — no substitutions, no partial credit. Like the Gita's final instruction to complete surrender (all words present, none missing), the window is valid only when every word from the sacred set is accounted for exactly. A single missing or extra word invalidates the window, just as partial surrender is not the same as complete refuge.