Extra Characters in a String

Medium
1489.

Extra Characters in a String

Extra Characters in a String is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {number}
 */
var minExtraChar = function(s, dictionary) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Extra Characters in a String — Problem & Solution

Extra Characters in a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Extra Characters in a String is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon, Google and Adobe interviews.

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

Hints for Extra Characters in a String

  1. Hint 1

    Let dp[i] be the fewest extra characters in the suffix s[i:].

  2. Hint 2

    Either character i is extra (1 + dp[i + 1]), or a dictionary word starts at i.

  3. Hint 3

    For every word w that matches at position i, dp[i] = min(dp[i], dp[i + len(w)]).

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]

Java

public static int minExtraChar(String s, String[] dictionary) {
    int n = s.length();
    int[] dp = new int[n + 1];
    for (int i = n - 1; i >= 0; i--) {
        int best = 1 + dp[i + 1];
        for (String w : dictionary) {
            if (s.startsWith(w, i) && dp[i + w.length()] < best) best = dp[i + w.length()];
        }
        dp[i] = best;
    }
    return dp[0];
}

C++

int minExtraChar(string s, vector<string>& dictionary) {
    int n = s.size();
    vector<int> dp(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        int best = 1 + dp[i + 1];
        for (const string& w : dictionary) {
            int len = w.size();
            if (i + len <= n && s.compare(i, len, w) == 0 && dp[i + len] < best) best = dp[i + len];
        }
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets