Extra Characters in a String

Medium · Tries · Explanation and code example

Dynamic Programming (Bottom-Up) Using Trie

How it works

This combines the bottom-up DP approach with Trie-based matching. We iterate from right to left, and at each position, we traverse the Trie to find all dictionary words that start at that position. The Trie allows early termination when no dictionary word can match the current prefix.

Steps

  1. Build a Trie from all dictionary words.
  2. Create an array dp of size n + 1, initialized to 0.
  3. For i from n - 1 down to 0:
    • Set dp[i] = 1 + dp[i + 1].
    • Start at the Trie root and traverse:
      • For j from i to n - 1:
        • If s[j] is not a child, break.
        • Move to the child node.
        • If this node marks a word end, update dp[i] = min(dp[i], dp[j + 1]).
  4. Return dp[0].

Complexity

  • Time complexity: O(n ^ 2 + m * k)
  • Space complexity: O(n + m * k)

Where n is the length of the string s, m is the number of words in the dictionary, and k is the average length of a word in the dictionary.

Things to watch for

Off-By-One Errors in Substring Boundaries

When checking if s[i:j+1] matches a dictionary word, getting the indices wrong is a common mistake. In Python, s[i:j] excludes index j, so you need s[i:j+1] to include the character at position j. Similarly, when jumping to the next position after a match, you should move to j+1, not j.

Not Considering the Skip-Character Option

At each position, you must always consider the option of skipping the current character (counting it as extra) with cost 1 + dp[i+1]. If you only check dictionary matches without this fallback, positions where no dictionary word starts will cause incorrect results or infinite loops.

Inefficient Substring Matching Without Memoization or Trie

The naive approach of checking all possible substrings against the dictionary for every position leads to exponential time complexity. Without memoization, the same subproblems are solved repeatedly. For large inputs, either use dynamic programming with memoization or build a Trie to efficiently find all dictionary words starting at each position.

Python code example

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word):
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.isWord = True

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        trie = Trie()
        for w in dictionary:
            trie.addWord(w)

        n = len(s)
        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            dp[i] = 1 + dp[i + 1]
            curr = trie.root
            for j in range(i, n):
                if s[j] not in curr.children:
                    break
                curr = curr.children[s[j]]
                if curr.isWord:
                    dp[i] = min(dp[i], dp[j + 1])

        return dp[0]

C++ code example

class TrieNode {
public:
    TrieNode* children[26];
    bool isWord;

    TrieNode() {
        for (int i = 0; i < 26; ++i) children[i] = nullptr;
        isWord = false;
    }
};

class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    void addWord(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (!curr->children[c - 'a']) {
                curr->children[c - 'a'] = new TrieNode();
            }
            curr = curr->children[c - 'a'];
        }
        curr->isWord = true;
    }
};

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        Trie trie;
        for (const string& word : dictionary) {
            trie.addWord(word);
        }

        int n = s.size();
        vector<int> dp(n + 1);
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = 1 + dp[i + 1];
            TrieNode* curr = trie.root;

            for (int j = i; j < n; ++j) {
                if (!curr->children[s[j] - 'a']) break;
                curr = curr->children[s[j] - 'a'];
                if (curr->isWord) {
                    dp[i] = min(dp[i], dp[j + 1]);
                }
            }
        }

        return dp[0];
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations