02. Extra Characters in a String

The problem can be found at the following link: Question Link

My Approach

Firstly we'll create a dp array to store immediate results which will be minExtra chars at a particular index.

1. Create a map of words in dictionary.

2. Now call a solve function.

3. In the solve function-

• If index is equal to size of the string, return 0 since we've completed our task

• if dp[index] != -1 we've already calculated our answer for this index so return dp[index]

• Now, create a empty string currStr, this will store string formed till current index

• minExtra stores the minimum size of extra chars required

• Iterate from cutIdx = 0 to s.size() and push the current character into our empty string.

• Now check if our currString is present in map or not, if it is our currExtra will be 0 , since no extra chars required, else it will be currStr.size().

• In nextExtra we're finding extra chars in the string that will be formed after the current string i.e from index cutIndex + 1 to s.size().

• totalExtra will be sum of the two calculate extras, i.e current and next.

• minExtra would store the minimum of all totalExtras.

• At last we return dp[index] = minExtra , here we are basically assigning minExtra to dp[index] and at the same time returning dp[index].

Time and Auxiliary Space Complexity

• Time Complexity: O(n)

• Auxiliary Space Complexity: O(n)

Code (C++)

class Solution {
public:
    int solve(string& s, unordered_map<string, int>&mp, vector<int>&dp, int index)
    {
        if (index >= s.size()) return 0;
        if (dp[index] != -1) return dp[index]; 
        
        string currStr = "";
        int minExtra = s.size();
        for (int cutIdx = index; cutIdx < s.size(); cutIdx++)
        {
            currStr.push_back(s[cutIdx]);

            int currExtra = (mp.count(currStr))? 0 : currStr.size();
            int nextExtra = solve(s, mp, dp, cutIdx + 1);
            int totalExtra = currExtra + nextExtra;
            
            minExtra = min(minExtra, totalExtra);
        }
        return dp[index] = minExtra;
    }
    int minExtraChar(string s, vector<string>& dictionary) 
    {
        vector<int>dp(s.size(), -1);
        unordered_map<string, int>mp;
        for (string& word : dictionary) mp[word]++;
        
        int ans = solve(s, mp, dp, 0);
        return ans;
        
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the rishabhv12/Daily-Leetcode-Solution repository.