Unique Substrings in Wraparound String - Practice Coding Problems

Unique Substrings in Wraparound String - Problem

We define the string base to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so base will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."

Given a string s, return the number of unique non-empty substrings of s that are present in base.

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

Input & Output

Example 1 — Basic Consecutive Sequence

$ Input: s = "abc"

› Output: 6

💡 Note: Substrings are: "a", "b", "c", "ab", "bc", "abc". All are consecutive in wraparound string, so answer is 6.

Example 2 — Wraparound Case

$ Input: s = "zabc"

› Output: 10

💡 Note: Includes wraparound: "z" → "a". Valid substrings: "z", "a", "b", "c", "za", "ab", "bc", "zab", "abc", "zabc". Total: 10.

Example 3 — Duplicate Characters

$ Input: s = "cac"

› Output: 2

💡 Note: Valid substrings are "c" and "a". Even though "c" appears twice, we only count unique substrings.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string s with lowercase letters

Find Valid Sequences

Identify consecutive sequences in wraparound alphabet

Count Unique Substrings

Sum all possible unique substrings from valid sequences

Key Takeaway

🎯 Key Insight: For each letter, track the maximum length of consecutive sequence ending at that letter, then sum all lengths

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to use dynamic programming to track the maximum length of valid wraparound sequence ending at each letter. Best approach uses O(n) time by maintaining current sequence length and updating max lengths. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(n²)	Generate all substrings and check if each is valid in wraparound string
Dynamic Programming - Track Max Length per Character	O(n)	O(1)	For each character, track the maximum length of valid sequence ending at that character

Brute Force - Check All Substrings — Algorithm Steps

Generate all possible substrings
For each substring, check if it's consecutive in wraparound alphabet
Use set to store unique valid substrings
Return size of set

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings from input string

Validate Each

Check if each substring is consecutive in wraparound alphabet

Count Unique

Use set to count only unique valid substrings

Code -

solution.c — C

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

int isValidSubstring(char* sub, int len) {
    if (len <= 1) return 1;
    for (int i = 1; i < len; i++) {
        if ((sub[i] - sub[i-1] + 26) % 26 != 1) {
            return 0;
        }
    }
    return 1;
}

int solution(char* s) {
    int n = strlen(s);
    char substrings[10000][105];
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int len = j - i;
            char substring[105];
            strncpy(substring, s + i, len);
            substring[len] = '\0';
            
            if (isValidSubstring(substring, len)) {
                int exists = 0;
                for (int k = 0; k < count; k++) {
                    if (strcmp(substrings[k], substring) == 0) {
                        exists = 1;
                        break;
                    }
                }
                if (!exists) {
                    strcpy(substrings[count], substring);
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char s[105];
    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, each taking O(n) time to validate

⚠ Quadratic Growth

Space Complexity

O(n²)

Set can store up to O(n²) unique substrings

⚠ Quadratic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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