Find Maximum Number of Non Intersecting Substrings

Find Maximum Number of Non Intersecting Substrings - Problem

You are given a string word. Return the maximum number of non-intersecting substrings of word that are at least four characters long and start and end with the same letter.

A substring is non-intersecting if it does not overlap with any other selected substring. The goal is to maximize the count of such valid substrings.

Input & Output

Example 1 — Basic Case

$ Input: word = "ababa"

› Output: 1

💡 Note: Valid substrings: "abab" (0-3), "baba" (1-4), "ababa" (0-4). Only one can be selected since they all overlap. Maximum count is 1.

Example 2 — Multiple Non-overlapping

$ Input: word = "abcabc"

› Output: 1

💡 Note: Valid substrings: "abca" (0-3), "bcab" (1-4), "cabc" (2-5). They all overlap, so maximum count is 1.

Example 3 — No Valid Substrings

$ Input: word = "abcd"

› Output: 0

💡 Note: No substring of length ≥ 4 starts and ends with the same character. Return 0.

Constraints

1 ≤ word.length ≤ 1000
word consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String with potential valid substrings

Find Valid

Identify all substrings ≥4 chars with same start/end letter

Select Non-overlapping

Choose maximum count of non-intersecting substrings

Key Takeaway

🎯 Key Insight: Transform string problem into interval scheduling - maximize non-overlapping intervals

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to treat this as an interval scheduling problem. Find all valid substrings (length ≥ 4, same start/end char), then use greedy selection by sorting intervals by end position. Best approach is Greedy with Time: O(n² log n), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Select Earliest Ending	O(n² log n)	O(n²)	Sort valid substrings by end position and greedily select non-overlapping ones
Dynamic Programming	O(n²)	O(n)	Use DP to track maximum substrings ending at each position
Brute Force - Try All Combinations	O(2^n)	O(n²)	Generate all valid substrings and try all possible non-overlapping combinations

Greedy - Select Earliest Ending — Algorithm Steps

Find all valid substrings (length ≥ 4, same start/end char)
Sort by ending position
Greedily select non-overlapping substrings
Return count of selected substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Find & Sort

Find all valid substrings and sort by end position

Greedy Selection

Select intervals that don't overlap with previous selections

Count Result

Return total count of selected substrings

Code -

solution.c — C

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

typedef struct {
    int start, end;
} Interval;

int compare(const void* a, const void* b) {
    Interval* ia = (Interval*)a;
    Interval* ib = (Interval*)b;
    return ia->end - ib->end;
}

int solution(char* word) {
    int n = strlen(word);
    Interval* intervals = (Interval*)malloc(n * n * sizeof(Interval));
    int intervalCount = 0;
    
    // Find all valid substrings
    for (int i = 0; i < n; i++) {
        for (int j = i + 4; j <= n; j++) {
            if (word[i] == word[j - 1]) {
                intervals[intervalCount++] = (Interval){i, j - 1};
            }
        }
    }
    
    // Sort by end position
    qsort(intervals, intervalCount, sizeof(Interval), compare);
    
    // Greedily select non-overlapping intervals
    int count = 0;
    int lastEnd = -1;
    
    for (int i = 0; i < intervalCount; i++) {
        if (intervals[i].start > lastEnd) {
            count++;
            lastEnd = intervals[i].end;
        }
    }
    
    free(intervals);
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

O(n²) to find all valid substrings, O(n² log n) to sort them

⚠ Quadratic Growth

Space Complexity

O(n²)

Storing up to O(n²) valid substrings in worst case

⚠ Quadratic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 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

Greedy - Select Earliest Ending — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler