Find Longest Self-Contained Substring - Practice Coding Problems

Find Longest Self-Contained Substring - Problem

Given a string s, your task is to find the length of the longest self-contained substring of s.

A substring t of a string s is called self-contained if:

t != s (the substring is not the entire string)
For every character in t, it doesn't exist in the rest of s (outside of t)

Return the length of the longest self-contained substring of s if it exists, otherwise return -1.

Input & Output

Example 1 — Basic Self-Contained

$ Input: s = "abcdef"

› Output: 5

💡 Note: The substring "abcde" (length 5) is self-contained because none of its characters (a,b,c,d,e) appear in the remaining part "f"

Example 2 — No Self-Contained

$ Input: s = "aaa"

› Output: -1

💡 Note: No substring can be self-contained because character 'a' appears throughout the entire string

Example 3 — Multiple Options

$ Input: s = "abcabc"

› Output: 3

💡 Note: Multiple substrings like "abc" (first occurrence) are self-contained, but none longer than 3 characters can avoid character overlap

Constraints

1 ≤ s.length ≤ 10³
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with various characters

Check Substrings

Find substrings where characters are isolated

Return Length

Length of longest valid substring or -1

Key Takeaway

🎯 Key Insight: A substring is self-contained when its characters don't appear anywhere else in the original string

Asked in

G Google 25 M Microsoft 18

The key insight is that a substring is self-contained when all its characters appear only within its boundaries and nowhere else in the string. The best approach uses character position tracking to efficiently verify boundaries. Time: O(n²), Space: O(k) where k is unique characters.

Common Approaches

Approach	Time	Space	Notes
✓ Two Pass with Hash Map	O(n³)	O(k)	Pre-compute character frequencies, then check substrings efficiently
Optimized Sliding Window	O(n²)	O(k)	Use character positions to efficiently find self-contained substrings
Brute Force	O(n³)	O(1)	Check every possible substring and verify if it's self-contained

Two Pass with Hash Map — Algorithm Steps

Build frequency map of entire string
For each substring, count its character frequencies
Check if any character appears both inside and outside the substring

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Frequency Map

Count all characters in string

Check Substrings

Compare substring vs total frequencies

Find Self-Contained

Characters don't exceed substring count

Code -

solution.c — C

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

int solution(char* s) {
    int n = strlen(s);
    int maxLength = -1;
    
    // Build frequency map of entire string (assuming ASCII)
    int totalFreq[256] = {0};
    for (int i = 0; i < n; i++) {
        totalFreq[(unsigned char)s[i]]++;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int subLen = j - i + 1;
            // Skip if substring equals entire string
            if (subLen == n) continue;
            
            // Count frequencies in substring
            int subFreq[256] = {0};
            for (int k = i; k <= j; k++) {
                subFreq[(unsigned char)s[k]]++;
            }
            
            // Check if substring is self-contained
            int isSelfContained = 1;
            for (int k = i; k <= j; k++) {
                unsigned char c = s[k];
                // If character appears outside substring
                if (totalFreq[c] > subFreq[c]) {
                    isSelfContained = 0;
                    break;
                }
            }
            
            if (isSelfContained) {
                if (subLen > maxLength) {
                    maxLength = subLen;
                }
            }
        }
    }
    
    return maxLength;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings × O(n) character frequency checking

⚠ Quadratic Growth

Space Complexity

O(k)

Hash map stores up to k unique characters

✓ Linear Space

24.5K Views

Medium Frequency

~25 min Avg. Time

680 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

Two Pass with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler