Index Pairs of a String - Practice Coding Problems

Index Pairs of a String - Problem

Given a string text and an array of strings words, return an array of all index pairs [i, j] so that the substring text[i...j] is in words.

Return the pairs [i, j] in sorted order (i.e., sort them by their first coordinate, and in case of ties sort them by their second coordinate).

Input & Output

Example 1 — Basic Case

$ Input: text = "thestoryofa", words = ["story","fleet","leetcode"]

› Output: [[3,7]]

💡 Note: Only "story" appears in text starting at index 3 and ending at index 7: text[3...7] = "story"

Example 2 — Multiple Matches

$ Input: text = "ababa", words = ["ab","ba"]

› Output: [[0,1],[1,2],[3,4]]

💡 Note: "ab" appears at [0,1] and "ba" appears at [1,2] and [3,4]. All pairs sorted by first coordinate, then second.

Example 3 — Overlapping Words

$ Input: text = "aaaa", words = ["aa","aaa"]

› Output: [[0,1],[0,2],[1,2],[1,3],[2,3]]

💡 Note: "aa" appears at [0,1], [1,2], [2,3] and "aaa" appears at [0,2], [1,3]. Results sorted naturally.

Constraints

1 ≤ text.length ≤ 100
1 ≤ words.length ≤ 20
1 ≤ words[i].length ≤ 50
text and words[i] consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Text string and array of target words to find

Process

Check all substrings against word list

Output

Sorted array of [start, end] index pairs

Key Takeaway

🎯 Key Insight: Use efficient lookup structures (hash set or Trie) to avoid repeated linear searches through the words array

Asked in

G Google 15 a Amazon 12

The key insight is to optimize word lookup by using either a hash set for O(1) checking or a Trie for efficient multi-pattern matching. The Hash Set approach converts the word list to a set and checks all substrings, achieving O(n³) time. The Trie approach builds a prefix tree and matches patterns more efficiently in O(n×L) time where L is the maximum word length.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Substring Check	O(n³ × m × k)	O(1)	Check every possible substring against every word in the list
Hash Set Optimization	O(n³)	O(m × k)	Use a hash set for O(1) word lookup instead of linear search
Trie-based Pattern Matching	O(n × L + m × k)	O(m × k)	Use a Trie to efficiently match multiple patterns simultaneously

Brute Force Substring Check — Algorithm Steps

Generate all substrings from each starting position
For each substring, search through words array
If found, add [start, end] to result
Sort the result pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings from text

Search Words

Check if each substring exists in words array

Collect Matches

Store index pairs for matching substrings

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* text, char words[][100], int wordCount, int result[][2]) {
    int count = 0;
    int n = strlen(text);
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            char substring[1001];
            strncpy(substring, text + i, j - i + 1);
            substring[j - i + 1] = '\0';
            
            for (int k = 0; k < wordCount; k++) {
                if (strcmp(words[k], substring) == 0) {
                    result[count][0] = i;
                    result[count][1] = j;
                    count++;
                    break;
                }
            }
        }
    }
    
    // Simple bubble sort
    for (int i = 0; i < count - 1; i++) {
        for (int j = 0; j < count - i - 1; j++) {
            if (result[j][0] > result[j+1][0] || 
                (result[j][0] == result[j+1][0] && result[j][1] > result[j+1][1])) {
                int temp0 = result[j][0], temp1 = result[j][1];
                result[j][0] = result[j+1][0]; result[j][1] = result[j+1][1];
                result[j+1][0] = temp0; result[j+1][1] = temp1;
            }
        }
    }
    
    return count;
}

int main() {
    char text[1001];
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = 0;
    
    char words[100][100];
    int wordCount = 0;
    // Simple parsing - assumes format like ["word1","word2"]
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int result[10000][2];
    int count = solution(text, words, wordCount, result);
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³ × m × k)

n² substrings, each taking O(n) to create, then O(m×k) to search through m words of average length k

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for iteration, result list not counted

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Substring Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler