Index Pairs of a String

Index Pairs of a String

What is this problem about?

The Index Pairs of a String coding problem asks you to find all occurrences of a set of words within a given text. For each match, you should return the starting and ending indices [i, j]. The final list of pairs must be sorted first by the starting index and then by the ending index.

Why is this asked in interviews?

Amazon use this "Easy" question to test string search foundations. It evaluates your ability to find substrings and handle overlapping matches (e.g., if "aba" and "ab" are both words, they both might match starting at the same index). It also checks your sorting skills for the final output.

Algorithmic pattern used

This is a String Matching problem. There are two common ways to solve it:

1. Iterative Search: For each word in the list, use text.indexOf(word) in a loop to find all occurrences.
2. Trie-based Search:
   • Insert all words into a Trie.
   • For each starting index $i$ in the text:
     • Walk through the Trie using characters starting from text[i].
     • Every time you hit a "word end" in the Trie, record the current index pair.

Example explanation

text = "ababa", words = ["aba", "ab"]

1. Start at index 0:
   • "ab" matches (ends at 1). Pair [0, 1].
   • "aba" matches (ends at 2). Pair [0, 2].
2. Start at index 1: No matches.
3. Start at index 2:
   • "ab" matches (ends at 3). Pair [2, 3].
   • "aba" matches (ends at 4). Pair [2, 4]. Final result: [[0, 1], [0, 2], [2, 3], [2, 4]].

Common mistakes candidates make

• Missing Overlaps: Using logic that "consumes" characters, preventing smaller or overlapping words from being detected.
• Sorting: Forgetting the two-level sorting requirement for the final list of pairs.
• Inefficiency: Using complex regex when simple Trie or indexOf logic is faster and easier to implement.

Interview preparation tip

Tries are the standard tool for "Multiple Pattern Matching." If you have many words to find in one text, using a Trie to check all words simultaneously for each starting position is much more efficient than searching for each word individually.