Extra Characters in a String

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazon

Problem 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 of the substrings.

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

Examples

Example 1:

Input: s = “leetscode”, dictionary = [“leet”,“code”,“leetcode”] Output: 1 Explanation: We can break s into “leet” and “code”, leaving ‘s’ as the extra character.

Example 2:

Input: s = “sayhelloworld”, dictionary = [“hello”,“world”] Output: 3 Explanation: We can break s into “hello” and “world”, leaving “say” (3 characters) as 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
All words in dictionary are unique

1D DP with Trie Prefix Matching

This is a classic partitioning optimization problem. Let dp[i] be the minimum extra characters for suffix s[i..n-1].

For each index i from n - 1 down to 0:

Option A (Skip): treat s[i] as an extra character. dp[i] = dp[i + 1] + 1.
Option B (Match): find any prefix of s[i..n-1] that matches a word in dictionary. If s[i..j] is in the dictionary, then dp[i] = min(dp[i], dp[j + 1]).

To find prefix matches efficiently, build a Trie containing all words from dictionary. For index i, traverse the Trie starting from s[i]. As you descend the Trie, whenever you reach a node marked as a complete word at index j, you can update dp[i] = min(dp[i], dp[j + 1]).

Solution: 1D DP with Trie

import java.util.*;

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }

    private void insert(TrieNode root, String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();
            }
            curr = curr.children[idx];
        }
        curr.isWord = true;
    }

    public int minExtraChar(String s, String[] dictionary) {
        int n = s.length();
        TrieNode root = new TrieNode();
        for (String word : dictionary) {
            insert(root, word);
        }

        int[] dp = new int[n + 1];
        // base case: dp[n] = 0 (no extra characters at end of string)

        for (int i = n - 1; i >= 0; i--) {
            // default option: treat s.charAt(i) as an extra character
            dp[i] = dp[i + 1] + 1;

            // search prefixes in Trie
            TrieNode curr = root;
            for (int j = i; j < n; j++) {
                int idx = s.charAt(j) - 'a';
                if (curr.children[idx] == null) break;
                curr = curr.children[idx];
                if (curr.isWord) {
                    dp[i] = Math.min(dp[i], dp[j + 1]);
                }
            }
        }

        return dp[0];
    }
}

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

class Solution:
    def minExtraChar(self, s: str, dictionary: list[str]) -> int:
        root = TrieNode()
        for word in dictionary:
            curr = root
            for char in word:
                if char not in curr.children:
                    curr.children[char] = TrieNode()
                curr = curr.children[char]
            curr.is_word = True

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

        for i in range(n - 1, -1, -1):
            # option 1: treat current char as extra
            dp[i] = dp[i + 1] + 1

            # option 2: match prefixes using the Trie
            curr = root
            for j in range(i, n):
                char = s[j]
                if char not in curr.children:
                    break
                curr = curr.children[char]
                if curr.is_word:
                    dp[i] = min(dp[i], dp[j + 1])

        return dp[0]

#include <vector>
#include <string>
#include <algorithm>

class Solution {
    struct TrieNode {
        TrieNode* children[26] = {};
        bool isWord = false;
    };

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

public:
    int minExtraChar(std::string s, std::vector<std::string>& dictionary) {
        int n = s.size();
        TrieNode* root = new TrieNode();
        for (const auto& word : dictionary) {
            insert(root, word);
        }

        std::vector<int> dp(n + 1, 0);

        for (int i = n - 1; i >= 0; i--) {
            dp[i] = dp[i + 1] + 1;

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

        return dp[0];
    }
};

Complexity Analysis:

Time Complexity: O(N² + W * L) where N is string length, W is dictionary size, and L is max word length. Building the Trie takes O(W * L). The DP transitions take O(N²) time since we iterate i from n-1 to 0 and traverse the Trie up to N times for each starting index.
Space Complexity: O(N + W * L) to store the DP array and the Trie nodes.