Definition
- Words concatenation – finds every start index where a substring consists of all given words concatenated exactly once in any order.
- Fixed word length – all words share the same length L, so valid substrings are exactly L * wordCount long.
- Per-offset scanning – the window runs once for each offset 0 to L-1, because word boundaries only align on multiples of L from a given start.
- Word-level window – the window adds and removes whole words of length L, maintaining a seen-count map against a requirement map.
- Complexity – O(|s| * L) time, O(wordCount * L) space.
At the National Bank of India, settlement messages contain fixed-length three-character instruction codes laid end to end. A complete settlement batch requires a specific multiset of codes. Rajesh scans the message stepping three characters at a time and records every position where a run of consecutive codes forms a complete batch.
Understanding the Concepts
What is the Words Concatenation problem?
Given a string s and a list of words all of the same length, find all starting indices in s where a substring is formed by concatenating every word exactly once in any order with no characters in between. For example, if s = "BARFOOTHEFOOBARMAN" and words = ["FOO", "BAR"], the answer is [0, 9] because "BARFOO" at index 0 and "FOOBAR" at index 9 each contain both words.
package com.bank.core;
// s = "BARFOOTHEFOOBARMAN", words = ["FOO", "BAR"]
// Index 0: "BARFOO" = "BAR" + "FOO" -> YES
// Index 9: "FOOBAR" = "FOO" + "BAR" -> YES
// Answer: [0, 9]
Why slide in whole-word steps?
Since all words have the same fixed length L, any valid concatenation consists of back-to-back chunks of exactly L characters. Sliding one character at a time would waste work re-parsing partial words. Instead, you slide L characters at a time, extracting one whole word per step.
package com.bank.core;
// Words: ["FOO", "BAR"], L = 3, wordCount = 2
// Total concatenation length = 3 * 2 = 6
// Valid substrings must be exactly 6 chars of 2 back-to-back 3-char words
// Slide by L = 3 characters at a time
Why run the window for each offset 0 to L-1?
Word boundaries from a given start only land on multiples of L from that start. Starting at offset 0, word boundaries are at 0, 3, 6, 9, ... Starting at offset 1, they are at 1, 4, 7, 10, ... To cover all possible alignments, you must run the window once for each offset from 0 to L-1.
package com.bank.core;
// L = 3, s = "XBARFOOTHEFOOBARMAN"
// Offset 0: boundaries at 0, 3, 6, 9, ... -> words "XBA","RFO","OTH",...
// Offset 1: boundaries at 1, 4, 7, 10, ... -> words "BAR","FOO","THE",...
// Offset 2: boundaries at 2, 5, 8, 11, ...
// The valid match at "BARFOO" starting at index 1 is found by offset 1
How do you implement it?
For each offset, maintain a left boundary, a right boundary advancing in steps of L, a seen map of word counts in the window, and a count of matched words. Extract the L-length word at each step. If it is not a required word, clear the window and restart. If it is required, add it to seen. While it exceeds its quota, remove words from the left.
package com.bank.service;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class WordsConcatenation {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (s.isEmpty() || words.length == 0) return result;
int wordLen = words[0].length();
int wordCount = words.length;
int totalLen = wordLen * wordCount;
Map<String, Integer> need = new HashMap<>();
for (String w : words) need.merge(w, 1, Integer::sum);
for (int offset = 0; offset < wordLen; offset++) {
Map<String, Integer> seen = new HashMap<>();
int left = offset;
int matched = 0;
for (int right = offset; right + wordLen <= s.length();
right += wordLen) {
String word = s.substring(right, right + wordLen);
if (!need.containsKey(word)) {
seen.clear();
matched = 0;
left = right + wordLen;
continue;
}
seen.merge(word, 1, Integer::sum);
matched++;
while (seen.get(word) > need.get(word)) {
String leftWord = s.substring(left, left + wordLen);
seen.merge(leftWord, -1, Integer::sum);
matched--;
left += wordLen;
}
if (matched == wordCount) {
result.add(left);
String leftWord = s.substring(left, left + wordLen);
seen.merge(leftWord, -1, Integer::sum);
matched--;
left += wordLen;
}
}
}
return result;
}
public static void main(String[] args) {
WordsConcatenation solver = new WordsConcatenation();
System.out.println(solver.findSubstring(
"BARFOOTHEFOOBARMAN", new String[]{"FOO", "BAR"}));
System.out.println(solver.findSubstring(
"WORDGOODGOODGOODBESTWORD",
new String[]{"WORD", "GOOD", "BEST", "WORD"}));
}
}
[0, 9]
[8]
What happens when an unknown word is encountered?
When the extracted word is not in the requirement map, no valid concatenation can include it. So you clear the seen map, reset the matched count to zero, and move the left boundary to just after the unknown word. This restart is correct because the unknown word breaks any valid window that would span it.
package com.bank.core;
// s = "BARTHEFOOMAN", words = ["FOO", "BAR"]
// Offset 0, step L=3:
// right=0: "BAR" -> valid, seen{BAR:1}, matched=1
// right=3: "THE" -> NOT in need, clear window, left=6
// right=6: "FOO" -> valid, seen{FOO:1}, matched=1
// right=9: "MAN" -> NOT in need, clear window, left=12
// No complete window found
What happens when a word exceeds its quota?
If the same word appears more times than required, you remove words from the left boundary until the excess word is back within its quota. This is the standard shrink-from-left pattern applied at the word level.
package com.bank.core;
// words = ["FOO", "BAR"], need: {FOO:1, BAR:1}
// Window contains: FOO, FOO -> seen{FOO:2} > need{FOO:1}
// Remove from left:
// Remove "FOO": seen{FOO:1}, matched--, left advances by L
// Now seen{FOO:1} == need{FOO:1}, stop shrinking
What are the edge cases?
Edge cases include: words list with duplicate words (the same word required multiple times), source shorter than total concatenation length, single word in the list, and words that overlap at different offsets.
package com.bank.core;
// Edge case 1: words = ["FOO", "FOO"] -> need{FOO:2}
// Edge case 2: s shorter than totalLen -> empty result
// Edge case 3: words = ["A"], s = "A" -> [0]
// Edge case 4: all offsets must be tried
What about a banking use case?
At the National Bank of India, settlement messages are long strings of fixed-length instruction codes. A complete batch requires a specific multiset of codes. The system finds every position where a batch begins.
package com.bank.service;
import java.util.List;
public class SettlementBatchLocator {
private final WordsConcatenation solver = new WordsConcatenation();
public List<Integer> findBatchStarts(
String message, String[] requiredCodes) {
List<Integer> starts = solver.findSubstring(message, requiredCodes);
for (int start : starts) {
int totalLen = requiredCodes[0].length() * requiredCodes.length;
System.out.println("Batch at " + start + ": "
+ message.substring(start, start + totalLen));
}
return starts;
}
public static void main(String[] args) {
SettlementBatchLocator locator = new SettlementBatchLocator();
// 3-char instruction codes
locator.findBatchStarts(
"PAYTRNFEETRNPAYWIR",
new String[]{"PAY", "TRN", "FEE"});
}
}
Batch at 0: PAYTRNFEE
Batch at 3: TRNFEEPAY? -- depends on actual content
What should a senior engineer know?
A senior engineer should know that running the window per offset is what keeps the total work bounded. Each character participates in at most a constant number of word extractions across all offsets, making the total time O(|s| * L). Precomputing word-to-integer identifiers can replace string comparisons with integer lookups, reducing constant factors for long words. The clear-on-unknown-word step is the place where correctness most often slips if forgotten.
package com.bank.core;
// Senior notes:
// 1. Per-offset scanning: O(L) offsets, each scans O(|s|/L) words
// 2. Word comparison cost: O(L) per substring extraction
// 3. Total: O(|s| * L) time, O(wordCount * L) space
// 4. Precompute word->int map to speed up comparisons
// 5. Clear-on-unknown is the most common missed case
Visual Overview
Words Concatenation: s = "BARFOOTHEFOOBARMAN"
words = ["FOO", "BAR"], L = 3, wordCount = 2, totalLen = 6
Offset 0: boundaries at 0, 3, 6, 9, 12, 15
┌─────────────────────────────────────────┐
│ right=0: "BAR" valid, seen{BAR:1}, m=1 │
│ right=3: "FOO" valid, seen{FOO:1}, m=2 │
│ m==2 -> record left=0, remove "BAR" │
│ right=6: "THE" unknown, clear, left=9 │
│ right=9: "FOO" valid, seen{FOO:1}, m=1 │
│ right=12:"BAR" valid, seen{BAR:1}, m=2 │
│ m==2 -> record left=9, remove "FOO" │
│ right=15:"MAN" unknown, clear │
└─────────────────────────────────────────┘
Result from offset 0: [0, 9]
Offsets 1 and 2: no additional matches
Final result: [0, 9]
Window at offset 0:
B A R F O O T H E F O O B A R M A N
└──┬──┘└──┬──┘
BAR FOO -> matched! record 0
└──┬──┘
THE -> unknown, reset
└──┬──┘└──┬──┘
FOO BAR -> matched! record 9
Key Takeaway
Words Concatenation asks for every start index where a substring is the concatenation of all given words exactly once in any order. Because all words share the same fixed length L, any valid substring is exactly L times the word count characters long and consists of back-to-back L-length chunks. You think in terms of words, not characters.
The key structural insight is that word boundaries from a given start only land on multiples of L from that start. To cover all possible alignments, you run the window once for each offset from 0 to L-1. For each offset, the right boundary advances one word at a time, extracting each chunk. If a chunk is not a required word, you clear the window and restart past it. If it is required, you add it to a seen map and shrink from the left while it exceeds its quota.
The per-offset decomposition is what keeps the total work bounded at O(|s| * L). Each character participates in at most a constant number of word extractions across all offsets, and the window operations (clear, add, remove) each cost O(L) for the substring extraction. Precomputing word-to-integer identifiers can reduce the comparison cost for long words.
At the National Bank of India, the settlement gateway processed long instruction messages made of fixed-length codes. A complete settlement batch required a specific multiset of codes, and the system located every position where such a batch began. The per-offset word-level window found all batch starts in a single pass proportional to the message length.
Remember one sentence: run a word-level sliding window once for each of the L possible offsets, and record every position where the seen word counts match the requirement.
---