2707. 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

Approach 01:

#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>

class Solution {
public:
    int minExtraChar(const std::string& str, const std::vector<std::string>& wordList) {
        int stringLength = str.size();
        std::unordered_set<std::string> wordSet(wordList.begin(), wordList.end());
        std::vector<int> dpArray(stringLength + 1, 0);

        for (int i = 1; i <= stringLength; ++i) {
            dpArray[i] = dpArray[i - 1] + 1;
            for (int j = 0; j < i; ++j) {
                if (wordSet.count(str.substr(j, i - j))) {
                    dpArray[i] = std::min(dpArray[i], dpArray[j]);
                }
            }
        }

        return dpArray[stringLength];
    }
};

class Solution:
    def minExtraChar(self, string: str, wordList: List[str]) -> int:
        stringLength = len(string)
        wordSet = set(wordList)
        dpArray = [0] * (stringLength + 1)

        for i in range(1, stringLength + 1):
            dpArray[i] = dpArray[i - 1] + 1
            for j in range(i):
                if string[j:i] in wordSet:
                    dpArray[i] = min(dpArray[i], dpArray[j])

        return dpArray[stringLength]

Time Complexity

• Outer Loop (Iterating Over String):

  The outer loop runs from 1 to stringLength (the size of the input string str), so it executes \(O(n)\) times, where \(n\) is the length of str.

• Inner Loop (Checking Substrings):

  For each position i, the inner loop runs from 0 to i-1, which results in a total of \(O(n^2)\) substring checks.

• Substring Search:

  Each substring search (using str.substr(j, i - j)) takes \(O(i – j)\), but the average length of substrings in a word set check is much smaller compared to n. In total, the checking of all substrings will take \(O(n^2)\).

• Checking in the Set:

  Checking whether a substring exists in the set wordSet is an \(O(1)\) operation.

• Overall Time Complexity:

  The dominant factor is the nested loops, leading to an overall time complexity of \(O(n^2)\), where \(n\) is the length of the input string.

Space Complexity

• Dynamic Programming Array:

  The dpArray has a size of \(n + 1\), where \(n\) is the length of the input string. This takes \(O(n)\) space.

• Word Set:

  The unordered_set stores the words from the word list, which takes \(O(m)\) space, where \(m\) is the total number of characters in the word list.

• Overall Space Complexity:

  The overall space complexity is \(O(n + m)\), where \(n\) is the length of the string and \(m\) is the total number of characters in the word list.