Extra Characters in a String

MEDIUM✓ CHIP-TIMEDLC #2707 — FULL STATEMENT ↗

The drill: Break a string into back-to-back chunks pulled from a dictionary, letting any characters that don't fit into a chunk go unmatched — find the split that leaves the fewest characters unmatched.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string and a dictionary of words arrive together. The task is to break the string into back-to-back chunks pulled from the dictionary, letting any leftover characters that don't fit into a chunk go unmatched, and find the split that leaves the fewest characters unmatched.

Chunks must be contiguous and drawn from the dictionary, they can't overlap, and a character that isn't covered by any chosen chunk simply counts against the leftover total — it isn't an error, just a cost.

Only the minimum possible count of leftover characters needs to be reported, not the split itself or which characters ended up unmatched.

EX 01

s = "sayhelloworld" · dictionary = ["hello", "world"]

→ 3

THE GREETING PREFIX 'S','A','Y' IS NEVER COVERED

EX 02

s = "abc" · dictionary = ["a", "b", "c"]

→ 0

EVERY CHARACTER IS ITS OWN DICTIONARY WORD

EX 03

s = "xyz" · dictionary = ["ab", "yz"]

→ 1

ONLY THE TAIL MATCHES, THE LEADING 'X' IS LEFT OVER

the string is short, generally well under a hundred characters
dictionary words are non-empty and may repeat as candidates
chunks pulled from the dictionary must be contiguous and non-overlapping
only the minimum leftover character count is returned, not the split

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every position in the string is either the start of some dictionary chunk or it's left over — that's a decision you can make right to left, remembering the best answer for every suffix.

HINT 2 THE STRUCTURE

Let dp[i] be the fewest leftover characters in s[i:]. Either s[i] itself is left over (dp[i+1] + 1), or some dictionary word starts exactly at i and hands off cleanly to dp[j] right after it ends.

HINT 3 ONE STEP FROM THE ANSWER

Insert every dictionary word into a trie once. Walking it character by character from each starting index i finds every word beginning there directly on the letters of s, without slicing or hashing a single substring.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE TRIE-BACKED FILLPATTERN · DP + TRIE WALK, RIGHT TO LEFTs = "abcd" · dictionary = [abc, ab, cd]

STEP 1

dp[i] = fewest leftover characters in s[i:]. dp[4], the empty tail, starts at 0 — the base case.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/extra-characters-in-a-string.py — RACE PACE

LANG ▸

PACE ▸

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:
            node = root
            for ch in word:
                node = node.children.setdefault(ch, TrieNode())
            node.is_word = True

        n = len(s)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            dp[i] = dp[i + 1] + 1  # s[i] left over
            node = root
            for j in range(i, n):
                ch = s[j]
                if ch not in node.children:
                    break
                node = node.children[ch]
                if node.is_word:
                    dp[i] = min(dp[i], dp[j + 1])
        return dp[0]

TIME O(N·L)SPACE O(Σ|DICTIONARY|)PYTHON · RACE PACE · 28 LN

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        words = set(dictionary)
        n = len(s)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            dp[i] = dp[i + 1] + 1  # s[i] left over
            for j in range(i + 1, n + 1):
                if s[i:j] in words:
                    dp[i] = min(dp[i], dp[j])
        return dp[0]

TIME O(N³)SPACE O(N + Σ|DICTIONARY|)PYTHON · TRAINING PACE · 11 LN

class ExtraCharsTrieNode {
    Map<Character, ExtraCharsTrieNode> children = new HashMap<>();
    boolean isWord = false;
}

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        ExtraCharsTrieNode root = new ExtraCharsTrieNode();
        for (String word : dictionary) {
            ExtraCharsTrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new ExtraCharsTrieNode());
            }
            node.isWord = true;
        }

        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = dp[i + 1] + 1; // s[i] left over
            ExtraCharsTrieNode node = root;
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (!node.children.containsKey(c)) {
                    break;
                }
                node = node.children.get(c);
                if (node.isWord) {
                    dp[i] = Math.min(dp[i], dp[j + 1]);
                }
            }
        }
        return dp[0];
    }
}

TIME O(N·L)SPACE O(Σ|DICTIONARY|)JAVA · RACE PACE · 35 LN

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        Set<String> words = new HashSet<>(Arrays.asList(dictionary));
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = dp[i + 1] + 1; // s[i] left over
            for (int j = i + 1; j <= n; j++) {
                if (words.contains(s.substring(i, j))) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            }
        }
        return dp[0];
    }
}

TIME O(N³)SPACE O(N + Σ|DICTIONARY|)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED