Find Special Substring of Length K - Practice Coding Problems

Find Special Substring of Length K - Problem

String Easy

You are given a string s and an integer k. Determine if there exists a substring of length exactly k in s that satisfies the following conditions:

The substring consists of only one distinct character (e.g., "aaa" or "bbb").
If there is a character immediately before the substring, it must be different from the character in the substring.
If there is a character immediately after the substring, it must also be different from the character in the substring.

Return true if such a substring exists. Otherwise, return false.

Input & Output

Example 1 — Valid Substring

$ Input: s = "aabbbcc", k = 3

› Output: true

💡 Note: Substring "bbb" at position 2-4 has length 3, all same character 'b', with different characters before (s[1]='a') and after (s[5]='c').

Example 2 — No Valid Substring

$ Input: s = "aaabbbccc", k = 4

› Output: false

💡 Note: No substring of length 4 with identical characters exists. Longest runs are of length 3.

Example 3 — Boundary Violation

$ Input: s = "aaaaa", k = 3

› Output: false

💡 Note: While "aaa" exists, any 3-character substring would have matching characters before or after, violating boundary conditions.

Constraints

1 ≤ s.length ≤ 1000
1 ≤ k ≤ s.length
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String s and target length k

Process

Find consecutive identical characters ≥ k length

Output

Return true if valid isolated substring exists

Key Takeaway

🎯 Key Insight: Track runs of consecutive identical characters and validate boundary isolation conditions

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to find runs of consecutive identical characters and check if any valid k-length substring can be isolated. Best approach uses single pass tracking for O(n) time complexity. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Single Pass Tracking	O(n)	O(1)	Track consecutive character runs in one pass
Brute Force - Check All Substrings	O(n×k)	O(1)	Check every possible substring of length k for validity

Optimized - Single Pass Tracking — Algorithm Steps

Iterate through string tracking current character and count
When count equals k, check if boundaries are valid
Reset count when character changes

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan

Find runs of identical characters

Check

For runs ≥ k length, check boundaries

Result

Return true if valid position found

Code -

solution.c — C

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

bool solution(char* s, int k) {
    int n = strlen(s);
    if (k > n) return false;
    
    int i = 0;
    while (i < n) {
        // Count consecutive identical characters
        char currentChar = s[i];
        int count = 1;
        int j = i + 1;
        
        while (j < n && s[j] == currentChar) {
            count++;
            j++;
        }
        
        // If we have at least k consecutive characters
        if (count >= k) {
            // Check all possible positions within this run
            for (int start = i; start <= j - k; start++) {
                // Check before boundary
                if (start > 0 && s[start - 1] == currentChar) {
                    continue;
                }
                
                // Check after boundary
                if (start + k < n && s[start + k] == currentChar) {
                    continue;
                }
                
                return true;
            }
        }
        
        i = j;
    }
    
    return false;
}

int main() {
    char s[1001];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    scanf("%d", &k);
    
    bool result = solution(s, k);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each character examined once

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current character and count

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

428 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

Optimized - Single Pass Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler