2707. Extra Characters in a String

NeetCode: Extra Characters in a String · LeetCode: 2707. Extra Characters in a String · Difficulty: Medium

Given a string s and an array of words dictionary, break s into non-overlapping substrings so that as many characters as possible belong to a dictionary word. Return the minimum number of leftover (extra) characters. Both s and the words use lowercase letters, and every word is non-empty.

Example

Input:  s = "leetscode", dictionary = ["leet", "code", "hs"]        Output: 1
        ("leet" + "code" are used, the "s" is extra)
Input:  s = "sayhelloworld", dictionary = ["hello", "world"]         Output: 3
        ("say" is extra)

Brute force: try every choice by recursion

Let f(i) be the minimum extras for the suffix starting at i. At position i, either leave s.charAt(i) as an extra character (1 + f(i + 1)), or, for each word that matches at i, skip over it (f(i + len)). Take the minimum. s.startsWith(w, i) tests whether w occurs at index i. Without caching, the same suffixes are solved repeatedly, so the running time is exponential.

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        return extrasFrom(s, dictionary, 0);
    }

    // Minimum extra characters in s.substring(i).
    private int extrasFrom(String s, String[] words, int i) {
        if (i == s.length()) return 0;
        int best = 1 + extrasFrom(s, words, i + 1); // s.charAt(i) is extra
        for (String w : words) {
            if (s.startsWith(w, i)) {
                best = Math.min(best, extrasFrom(s, words, i + w.length()));
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minExtraChar("leetscode", new String[] {"leet", "code", "hs"}));
        System.out.println(solution.minExtraChar("sayhelloworld", new String[] {"hello", "world"}));
        System.out.println(solution.minExtraChar("", new String[] {"a"}));
    }
}

1
3
0

Time: exponential in n in the worst case. Space: O(n) recursion depth.

Better: DP over a HashSet of words

There are only n + 1 distinct subproblems, so store their answers. Define dp[i] as the minimum extras for the prefix s.substring(0, i). Then dp[i] = dp[i-1] + 1 (last character extra), or dp[i] = dp[j] for every j < i where s.substring(j, i) is in the dictionary. A HashSet<String> answers "is this substring a word?", but substring copies its characters and hashing a string reads all of them, so each check costs time proportional to the substring's length.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        Set<String> set = new HashSet<>();
        for (String w : dictionary) set.add(w);
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 0; j < i; j++) {
                if (set.contains(s.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            }
        }
        return dp[n];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minExtraChar("leetscode", new String[] {"leet", "code", "hs"}));
        System.out.println(solution.minExtraChar("sayhelloworld", new String[] {"hello", "world"}));
        System.out.println(solution.minExtraChar("", new String[] {"a"}));
    }
}

1
3
0

Time: O(n^3): O(n^2) substrings, each copied and hashed in O(n). Space: O(n + total dictionary length).

Optimal: DP with a trie

Most substrings checked by the set version are not a prefix of any word. A trie of the dictionary avoids them. Fill dp from the back, where dp[i] is the minimum extras for the suffix s.substring(i). Start with dp[i] = dp[i+1] + 1 (s.charAt(i) extra), then walk the trie along s.charAt(i), s.charAt(i+1), .... The walk stops when the next letter has no child. Each time it reaches a word end after s.charAt(j), set dp[i] = Math.min(dp[i], dp[j + 1]).

The walk from any i is at most L steps, the length of the longest word, and no substring is built or hashed. The trie is stored in arrays: next[node][letter] holds the child node number, where 0 means "no child" because the root (node 0) is never a child. The number of nodes is at most the total length of the words plus one, so the arrays are sized from that.

Trace for leetscode (indices 0-8) with leet, code, hs: dp[9] = 0; dp[8] = 1, dp[7] = 2, dp[6] = 3 (no word starts with e, d, o). At i = 5 the walk c-o-d-e reaches a word end at j = 8, so dp[5] = dp[9] = 0. dp[4] = dp[5] + 1 = 1 (the s), then dp[3] = 2, dp[2] = 3, dp[1] = 4. At i = 0 the walk l-e-e-t reaches a word end at j = 3, so dp[0] = min(dp[1] + 1, dp[4]) = 1.

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        int total = 0;
        for (String w : dictionary) total += w.length();
        int[][] next = new int[total + 1][26]; // next[node][letter] = child node, 0 = none
        boolean[] end = new boolean[total + 1]; // end[node] = a word ends here
        int nodes = 1;
        for (String w : dictionary) {
            int node = 0;
            for (int k = 0; k < w.length(); k++) {
                int c = w.charAt(k) - 'a';
                if (next[node][c] == 0) next[node][c] = nodes++;
                node = next[node][c];
            }
            end[node] = true;
        }

        int n = s.length();
        int[] dp = new int[n + 1]; // dp[i] = minimum extras in s.substring(i)
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = dp[i + 1] + 1;
            int node = 0;
            for (int j = i; j < n; j++) {
                node = next[node][s.charAt(j) - 'a'];
                if (node == 0) break;
                if (end[node]) dp[i] = Math.min(dp[i], dp[j + 1]);
            }
        }
        return dp[0];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minExtraChar("leetscode", new String[] {"leet", "code", "hs"}));
        System.out.println(solution.minExtraChar("sayhelloworld", new String[] {"hello", "world"}));
        System.out.println(solution.minExtraChar("", new String[] {"a"}));
    }
}

1
3
0

Time: O(n * L + total dictionary length), where L is the longest word (at most O(n^2), versus O(n^3) for the set version). Space: O(n + trie size).

Edge cases

• Empty string: the answer is 0.
• No word matches: every character is extra, so the answer is n.
• Overlapping words (leet and leetcode): the DP takes the minimum over all matches at each position.
• Input is lowercase ASCII, so a 26-slot child array is enough. A character outside a to z would throw ArrayIndexOutOfBoundsException.

How to explain it in an interview

• Define dp[i] as the minimum extras for a prefix or suffix; each position either is extra or ends or starts a dictionary word.
• Plain recursion repeats subproblems and is exponential; there are only n + 1 distinct states.
• Checking every substring against a HashSet gives O(n^3) because each substring copy and hash costs O(length).
• A trie walk from each start position stops as soon as no word has that prefix, so each start does at most L steps.
• The result is O(n * L + total dictionary length) time and O(n + trie size) space.