Repeated String Match - Practice Coding Problems

Repeated String Match - Problem

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it.

If it is impossible for b to be a substring of a after repeating it, return -1.

Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".

Input & Output

Example 1 — Basic Case

$ Input: a = "abcd", b = "cdabcdab"

› Output: 3

💡 Note: We need "abcdabcdabcd" (3 repetitions) to contain "cdabcdab" as substring

Example 2 — Single Repetition

$ Input: a = "abc", b = "cab"

› Output: 2

💡 Note: "abc" repeated once gives "abc", doesn't contain "cab". "abcabc" contains "cab"

Example 3 — Impossible Case

$ Input: a = "abc", b = "aabcd"

› Output: -1

💡 Note: Character 'd' in b doesn't exist in a, so impossible to form b from repetitions of a

Constraints

1 ≤ a.length, b.length ≤ 10⁴
a and b consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String a to repeat, string b to find

Process

Repeat a until b is found as substring

Output

Minimum repetitions needed or -1 if impossible

Key Takeaway

🎯 Key Insight: You need at most ceil(len(b)/len(a)) + 1 repetitions to find any possible substring

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that we need at most ceil(len(b)/len(a)) + 1 repetitions. Best approach validates character sets first, then tests only the minimum required bounds. Time: O(n+m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Character Set Validation + Bounded Search	O(n + m)	O(1)	First check if all characters in b exist in a, then search within calculated bounds
Brute Force Concatenation	O(n × m × k)	O(n × k)	Keep concatenating string a until b is found or length exceeds reasonable limit

Character Set Validation + Bounded Search — Algorithm Steps

Check if all characters in b exist in a
Calculate minimum repetitions needed: ceil(len(b)/len(a))
Calculate maximum repetitions needed: min_reps + 1
Test only within these bounds

Visualization

Tap to expand

Step-by-Step Walkthrough

Validate

Check if all chars in b exist in a

Calculate

Find min and max repetitions needed

Test

Only test within calculated bounds

Code -

solution.c — C

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

int solution(char* a, char* b) {
    if (strlen(b) == 0) return 0;
    if (strlen(a) == 0) return -1;
    
    int lenA = strlen(a);
    int lenB = strlen(b);
    
    // Check if all characters in b exist in a
    bool charExists[256] = {false};
    for (int i = 0; i < lenA; i++) {
        charExists[(unsigned char)a[i]] = true;
    }
    
    for (int i = 0; i < lenB; i++) {
        if (!charExists[(unsigned char)b[i]]) {
            return -1;
        }
    }
    
    // Calculate bounds
    int minReps = (lenB + lenA - 1) / lenA; // Ceiling division
    int maxReps = minReps + 1;
    
    // Test within bounds
    int repsToTest[] = {minReps, maxReps};
    for (int i = 0; i < 2; i++) {
        int reps = repsToTest[i];
        char* repeated = malloc((lenA * reps + 1) * sizeof(char));
        repeated[0] = '\0';
        
        for (int j = 0; j < reps; j++) {
            strcat(repeated, a);
        }
        
        if (strstr(repeated, b) != NULL) {
            free(repeated);
            return reps;
        }
        free(repeated);
    }
    
    return -1;
}

int main() {
    char a[1001], b[1001];
    fgets(a, sizeof(a), stdin);
    fgets(b, sizeof(b), stdin);
    
    // Remove newlines
    a[strcspn(a, "\n")] = 0;
    b[strcspn(b, "\n")] = 0;
    
    int result = solution(a, b);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

One pass to check character sets, then at most 2 substring checks of length O(n+m)

✓ Linear Growth

Space Complexity

O(1)

Only using character set for validation, no extra string storage

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 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

Character Set Validation + Bounded Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler