Count Substrings Without Repeating Character

Count Substrings Without Repeating Character - Problem

You are given a string s consisting only of lowercase English letters. We call a substring special if it contains no character which has occurred at least twice (in other words, it does not contain a repeating character).

Your task is to count the number of special substrings.

For example, in the string "pop", the substring "po" is a special substring, however, "pop" is not special (since 'p' has occurred twice).

Return the number of special substrings.

A substring is a contiguous sequence of characters within a string. For example, "abc" is a substring of "abcd", but "acd" is not.

Input & Output

Example 1 — Basic Case

$ Input: s = "abca"

› Output: 7

💡 Note: Special substrings are: "a" (at index 0), "ab", "abc", "b", "bc", "bca", "a" (at index 3). Total count is 7.

Example 2 — All Same Character

$ Input: s = "aaa"

› Output: 3

💡 Note: Only single characters are special: "a" at index 0, "a" at index 1, "a" at index 2. Any longer substring contains repeating characters.

Example 3 — All Unique Characters

$ Input: s = "abc"

› Output: 6

💡 Note: All substrings are special: "a", "ab", "abc", "b", "bc", "c". Total count is 6.

Constraints

1 ≤ s.length ≤ 10⁴
s consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with potentially repeating characters

Find Valid Substrings

Identify all substrings with unique characters only

Count Total

Return the total count of special substrings

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently count valid substrings ending at each position

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to use a sliding window approach with hash map to efficiently count substrings without repeating characters. Best approach uses two pointers to maintain a valid window and count all substrings ending at each position. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(n)	Generate all possible substrings and check each for unique characters
Optimized Sliding Window	O(n)	O(1)	Use two pointers with hash map to efficiently count all valid substrings
Sliding Window with Hash Map	O(n²)	O(1)	Use expanding window to count substrings ending at each position

Brute Force - Check All Substrings — Algorithm Steps

For each starting position i
For each ending position j >= i
Check if substring s[i:j+1] has unique characters using a set
If unique, increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings from each starting position

Check Uniqueness

Use set to verify all characters are unique

Count Valid

Increment counter for each valid substring

Code -

solution.c — C

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

int solution(char* s) {
    int count = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int chars[26] = {0};
            int unique = 1;
            
            for (int k = i; k <= j; k++) {
                if (chars[s[k] - 'a'] > 0) {
                    unique = 0;
                    break;
                }
                chars[s[k] - 'a'] = 1;
            }
            
            if (unique) {
                count++;
            }
        }
    }
    
    return count;
}

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³)

Two nested loops to generate O(n²) substrings, and O(n) to check each substring

⚠ Quadratic Growth

Space Complexity

O(n)

Set to store characters for uniqueness checking

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 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

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler