Extra Characters in a String

Explanation & Solution

Description

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 substring.

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

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

leet

code

leetcode

Output: 1

Explanation: We can break s into "leet" + "s" + "code". There is 1 extra character "s", so we return 1.

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

Approach

Trie pattern

1. Build a Trie from the Dictionary

Insert every word from dictionary into a trie
Each node stores children and an isEnd flag marking complete words
The trie enables efficient prefix matching against the string

2. Define the DP State

Let dp[i] = minimum extra characters in the substring s[i..n-1]
Base case: dp[n] = 0 (empty suffix has 0 extra characters)
Process from right to left (i = n-1 down to 0)

3. Default: Skip the Current Character

If we don't match any dictionary word starting at index i, the character is extra
So dp[i] = dp[i + 1] + 1 as the default

4. Try Matching Dictionary Words Using the Trie

From index i, traverse the trie character by character through s[i], s[i+1], ...
If the trie path breaks (no matching child), stop
Whenever we reach a node marked isEnd, a dictionary word s[i..j] is matched
Update dp[i] = min(dp[i], dp[j + 1]) — use this word and continue from j + 1

5. Return the Answer

dp[0] gives the minimum extra characters for the entire string

Key Insight

The trie lets us check all dictionary words starting at index i simultaneously in a single traversal, avoiding redundant comparisons
Combined with DP, this yields an **O(n * L) solution where L is the max word length, compared to O(n * m * L)** without the trie (m = dictionary size)

Visualization

Input:

[l, e, e, t, s, c, o, d, e]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Design File System

Number of Distinct Substrings in a String