Extra Characters in a String

MEDIUM

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.

Example 1:

Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Example 2:

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.

Constraints:

1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
dictionary[i] and s consists of only lowercase English letters
dictionary contains distinct words

Approaches

Checkout 3 different approaches to solve Extra Characters in a String. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Recursion

This approach directly translates the problem into a recursive structure. We explore all possible ways to partition the string. At each position, we decide whether to skip the character (counting it as extra) or to match it as part of a dictionary word. This exhaustive search explores every possibility to find the minimum number of extra characters.

Algorithm

Define a recursive function solve(startIndex) that calculates the minimum extra characters for the suffix of s starting from startIndex.
Base Case: If startIndex reaches the end of the string (s.length()), it means we have processed the entire string, so we return 0.
Recursive Step: For any startIndex, we have two main choices:
1. Treat the character s[startIndex] as an extra character. The cost for this choice is 1 + solve(startIndex + 1).
2. Try to form a word from the dictionary starting at startIndex. We iterate through all possible end indices j from startIndex to s.length() - 1. If the substring s.substring(startIndex, j + 1) exists in the dictionary, this is a valid move. The cost for this choice is solve(j + 1), as the characters in the word are not extra.
The function returns the minimum cost among all possible choices.

The core idea is to define a function, let's say solve(i), which computes the minimum extra characters for the suffix of the string s starting at index i. To compute solve(i), we consider two possibilities. First, we can treat the character s[i] as an extra character. In this case, the total number of extra characters will be 1 (for s[i]) plus the result of the subproblem for the rest of the string, which is solve(i+1). Second, we can try to match a word from the dictionary that starts at index i. We check every substring s[i...j] (for j from i to n-1) against the dictionary. If a match is found, we've successfully covered that part of the string with zero extra characters, and we recursively call solve(j+1) to handle the remainder of the string. The final result for solve(i) is the minimum value obtained from all these possibilities. The initial call would be solve(0).

Complexity Analysis

Time Complexity: O(2^n * n * k), where n is the length of `s` and k is the average length of a dictionary word. The complexity is exponential because at each character, the function can branch, leading to a number of calls that grows exponentially with `n`. The additional factors account for substring creation and dictionary lookups.Space Complexity: O(n), where n is the length of the string `s`. This space is used by the recursion call stack.

Pros and Cons

Pros:

Simple to understand and implement as it directly models the problem's decision-making process.

Cons:

Extremely inefficient due to the massive number of redundant computations for the same subproblems.
Will lead to a 'Time Limit Exceeded' (TLE) error on any reasonably sized input.

Code Solutions

Checking out 4 solutions in different languages for Extra Characters in a String. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Extra Characters in a String

Patterns:

Dynamic Programming

Data Structures:

ArrayHash TableStringTrie

Companies:

PornHub |