2707. Extra Characters in a String LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2707. Extra Characters in a String LeetCode Solution with the best time and space complexity. The solution to Extra Characters in a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Extra Characters in a String solution in C++
Extra Characters in a String solution in Java
Extra Characters in a String solution in Python
Additional Resources

2707. Extra Characters in a String LeetCode Solution image

Problem Statement of Extra Characters in a String

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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n)

2707. Extra Characters in a String LeetCode Solution in C++

class Solution {
 public:
  // Similar to 139. Word Break
  int minExtraChar(string s, vector<string>& dictionary) {
    const int n = s.length();
    const unordered_set<string> dictionarySet{dictionary.begin(),
                                              dictionary.end()};
    // dp[i] := the minimum extra letters if breaking up s[0..i) optimally
    vector<int> dp(n + 1, n);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i)
      for (int j = 0; j < i; ++j)
        // s[j..i) is in `dictionarySet`.
        if (dictionarySet.contains(s.substr(j, i - j)))
          dp[i] = min(dp[i], dp[j]);
        // s[j..i) are extra letters.
        else
          dp[i] = min(dp[i], dp[j] + i - j);

    return dp[n];
  }
};
/* code provided by PROGIEZ */

2707. Extra Characters in a String LeetCode Solution in Java

class Solution {
  // Similar to 139. Word Break
  public int minExtraChar(String s, String[] dictionary) {
    final int n = s.length();
    Set<String> dictionarySet = new HashSet<>(Arrays.asList(dictionary));
    // dp[i] := the minimum extra letters if breaking up s[0..i) optimally
    int[] dp = new int[n + 1];
    Arrays.fill(dp, n);
    dp[0] = 0;

    for (int i = 1; i <= n; i++)
      for (int j = 0; j < i; j++)
        // s[j..i) is in `dictionarySet`.
        if (dictionarySet.contains(s.substring(j, i)))
          dp[i] = Math.min(dp[i], dp[j]);
        // s[j..i) are extra letters.
        else
          dp[i] = Math.min(dp[i], dp[j] + i - j);

    return dp[n];
  }
}
// code provided by PROGIEZ

2707. Extra Characters in a String LeetCode Solution in Python

class Solution:
  # Similar to 139. Word Break
  def minExtraChar(self, s: str, dictionary: list[str]) -> int:
    n = len(s)
    dictionarySet = set(dictionary)
    # dp[i] := the minimum extra letters if breaking up s[0..i) optimally
    dp = [0] + [n] * n

    for i in range(1, n + 1):
      for j in range(i):
        if s[j:i] in dictionarySet:
          dp[i] = min(dp[i], dp[j])
        else:
          dp[i] = min(dp[i], dp[j] + i - j)

    return dp[n]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents