Extra Characters in a String - Practice Coding Problems

Extra Characters in a String - Problem

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.

Input & Output

Example 1 — Basic Case

$ Input: s = "leetscode", dictionary = ["leet", "code", "leetcode"]

› Output: 1

💡 Note: We can break s into "leet" + "s" + "code". The character "s" is not in the dictionary, so we have 1 extra character.

Example 2 — Perfect Match

$ Input: s = "sayhelloworld", dictionary = ["hello", "world"]

› Output: 3

💡 Note: We can break s into "say" + "hello" + "world". The substring "say" has 3 extra characters.

Example 3 — No Dictionary Words

$ Input: s = "abc", dictionary = ["def", "ghi"]

› Output: 3

💡 Note: No words from dictionary can be used, so all 3 characters are extra.

Constraints

1 ≤ s.length ≤ 50
1 ≤ dictionary.length ≤ 50
1 ≤ dictionary[i].length ≤ 50
dictionary[i] and s consist of only lowercase English letters
dictionary contains distinct words

Visualization

Tap to expand

Understanding the Visualization

Input

String "leetscode" and dictionary ["leet", "code", "leetcode"]

Process

Find optimal way to use dictionary words and minimize extra characters

Output

Minimum extra characters = 1

Key Takeaway

🎯 Key Insight: Use dynamic programming to find the optimal way to split the string, minimizing characters that don't belong to any dictionary word.

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to use dynamic programming where each position represents the minimum extra characters needed from that point to the end. We can either skip the current character (adding 1 to extra count) or use a dictionary word starting at that position. The optimal approach is bottom-up DP with Time: O(n²×m), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2^n)	O(n)	Try all possible ways to split the string into dictionary words
Top-Down DP with Memoization	O(n² × m)	O(n + m)	Same as brute force but cache results to avoid recomputation
Bottom-Up Dynamic Programming	O(n² × m)	O(n + m)	Build solution iteratively from end to beginning using 1D DP array

Brute Force Recursion — Algorithm Steps

Step 1: For each position, try skipping current character (add 1 to extra count)
Step 2: Try each dictionary word that matches substring starting at current position
Step 3: Recursively solve for remaining string and take minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at index 0

Consider skipping 'l' or finding words starting with 'l'

Try all options

Recursively explore skip vs use word paths

Return minimum

Take the path with minimum extra characters

Code -

solution.c — C

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

char dictionary[1000][51];
int dictSize = 0;

int isInDict(char* word) {
    for (int i = 0; i < dictSize; i++) {
        if (strcmp(dictionary[i], word) == 0) {
            return 1;
        }
    }
    return 0;
}

int backtrack(char* s, int index, int len) {
    if (index == len) {
        return 0;
    }
    
    // Option 1: Skip current character
    int minExtra = 1 + backtrack(s, index + 1, len);
    
    // Option 2: Try dictionary words
    for (int end = index + 1; end <= len; end++) {
        char substring[51];
        strncpy(substring, s + index, end - index);
        substring[end - index] = '\0';
        
        if (isInDict(substring)) {
            int result = backtrack(s, end, len);
            if (result < minExtra) {
                minExtra = result;
            }
        }
    }
    
    return minExtra;
}

int solution(char* s, char dict[][51], int dictLen) {
    dictSize = dictLen;
    for (int i = 0; i < dictLen; i++) {
        strcpy(dictionary[i], dict[i]);
    }
    return backtrack(s, 0, strlen(s));
}

int main() {
    char s[51];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char dictLine[1000];
    fgets(dictLine, sizeof(dictLine), stdin);
    
    // Simple parsing for dictionary
    char dict[100][51];
    int dictLen = 0;
    char* token = strtok(dictLine, "[],\" \n");
    while (token != NULL && dictLen < 100) {
        if (strlen(token) > 0) {
            strcpy(dict[dictLen++], token);
        }
        token = strtok(NULL, "[],\" \n");
    }
    
    printf("%d\n", solution(s, dict, dictLen));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

For each character, we have 2 choices (skip or use), leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion call stack can go up to n levels deep

⚡ Linearithmic Space

28.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 Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler