Get started

Extra Characters in a String — Medium Problem & Solution

You are given a string s and a list of words dictionary. Break s into one or more non-overlapping substrings such that each substring is a word in…

Problem statement

You are given a string s and a list of words dictionary. Break s into one or more non-overlapping substrings such that each substring is a word in dictionary; characters of s that end up in no chosen substring are extra.

Return the minimum possible number of extra characters.

Example 1

Input: s = "dsaroadmap", dictionary = ["road","map","ds"]
Output: 1
Explanation: `ds` + `road` + `map` leave only the `a` at index 2 unused.

Example 2

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: `say` is left over.

Example 3

Input: s = "codekairo", dictionary = ["code","kair","kai","ro"]
Output: 0

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

How to solve Extra Characters in a String

Suffix DP over positions: at each index you either throw the character away or consume a whole dictionary word that starts there.

Approach

  1. dp[n] = 0.
  2. For i = n-1 down to 0: start with dp[i] = 1 + dp[i + 1].
  3. For each dictionary word w with s starting with w at i, set dp[i] = min(dp[i], dp[i + |w|]).
  4. Return dp[0].

Why it works

In an optimal break-up, position i is either unused (cost 1 plus the best for the rest) or the start of some chosen word, after which the rest is again an independent suffix problem. The DP tries both, so it finds the optimum.

Complexity

  • Time — O(n · D · L) — n positions, D words of length up to L (a trie makes it O(n²))
  • Space — O(n)

Pitfalls

  • Greedily taking the longest word that matches can be wrong — a shorter word may let a later word fit.
  • Words may be longer than the rest of s; check bounds before comparing.
  • Characters inside a chosen word are never extra, but chosen words cannot overlap.

Reference solution

Python

from typing import List

def minExtraChar(s: str, dictionary: List[str]) -> int:
    n = len(s)
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        best = 1 + dp[i + 1]
        for w in dictionary:
            if s.startswith(w, i) and dp[i + len(w)] < best:
                best = dp[i + len(w)]
        dp[i] = best
    return dp[0]

JavaScript

var minExtraChar = function(s, dictionary) {
    var n = s.length;
    var dp = new Array(n + 1).fill(0);
    for (var i = n - 1; i >= 0; i--) {
        var best = 1 + dp[i + 1];
        for (var k = 0; k < dictionary.length; k++) {
            var w = dictionary[k];
            if (i + w.length <= n && s.substr(i, w.length) === w && dp[i + w.length] < best) best = dp[i + w.length];
        }
        dp[i] = best;
    }
    return dp[0];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 424 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming