Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Extra Characters in a String

Problem Statement

Given a string s and an array of words words. Break string s into multiple non-overlapping substrings such that each substring should be part of the words. There are some characters left which are not part of any substring.

Return the minimum number of remaining characters in s, which are not part of any substring after string break-up.

Examples

  1. Example 1:
    • Input: s = "amazingracecar", dictionary = ["race", "car"]
    • Expected Output: 7
    • Justification: The string `s

.....

.....

.....

Like the course? Get enrolled and start learning!
L

lestatcheb

· 2 years ago

Looks like we don't have any DP sections before, and here we just starting using DP solution without knowing any DP concepts.

I think we should either remove this DP solution and use another one (like Trie with 2 pointers),

or add DP learning section somewhere before this Trie learning section

D

dlflann

· 2 years ago

An approach similar to the last problem, Index Pairs, could be used here. Simply iterating forward through the string and comparing the characters to the trie is enough to determine whether it exist in the dictionary or not. Then just keep a running total of the lengths of each word matched found in the trie, the length of the string minus this total gives you the left over letter count. This can be done without the use of an additioinal data structure, the DP array.

Show 3 replies
M

Mike

· 2 years ago

The description & test cases create a little ambiguity where it would seem the use of a trie is overkill. For example, this code passes all test cases:

public int minExtraChar(String str, String[] dictionary) {
        int count = 0;
        for (String word : dictionary) {
            count += word.length();
        }
        return str.length() - count;
    }
Show 1 reply
L

Lee

· 2 years ago

I think this could fail under certain test cases, however.


class Solution:
    def minExtraChar(self, s, dictionary):
        # build the Trie
        root = TrieNode()
        for word in dictionary:
            node = root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.isEnd = True

        # iterate over string counting unused characters
        totalUnused = 0
        curUnused = 0
        node = root
        for ch in s:
            curUnused += 1
            if ch not in node.children:
                totalUnused += curUnused
                curUnused = 0
                node = root
                continue
            node = node.child
Steve Ochoa

Steve Ochoa

· 2 years ago

In the Python solution, you perform an "i=j" java/c/c++ style reassignment when the success condition is met. However, this does not work in a Python range loop. The loop counter will always be set to the next value in the range sequence at the start of every loop iteration, regardless of any reassignment of the loop counter value within the loop. Granted, your solution still works, but this may be a big "gotcha" during an interview.

Example:

j = 999
for i in range(10):
		print(f'top={i}')
		i = j
		print(f'after={i}')

Will output:

top=0
after=999
top=1
after=999
top=2
after=999
top=3
...
Show 2 replies
K

Kai

· 2 years ago

The current C++ suggested solution uses Greedy algorithm with Trie structure but that doesn't cover all cases.

For example, when the input string s is "ecolloycollotkvzqpdaumuqgs" and the dictionary is ["flbri","uaaz","numy","laper","ioqyt","tkvz","ndjb","gmg","gdpbo","x","collo","vuh","qhozp","iwk","paqgn","m","mhx","jgren","qqshd","qr","qpdau","oeeuq","c","qkot","uxqvx","lhgid","vchsk","drqx","keaua","yaru","mla","shz","lby","vdxlv","xyai","lxtgl","inz","brhi","iukt","f","lbjou","vb","sz","ilkra","izwk","muqgs","gom","je"], the current Greedy solution returns 14 instead of 2.

This is because, in Greedy approach, the mapping characters are "c" "c" "tkvz", "qpdau" and "m".

However, this is not the maximum mapping character case: "collo", "collo", "tkvz", "qpdau" "muqgs" which left only

L

lejafilip

· 2 years ago

As above: ("leetspcode", { "leet","eetsp", "code","leetcode" }). Your code returns 2 but should return 1;

This is next example while your code is wrong or doesn't cover most optimal solution (so it is usseless at FAANG interview). Please fix that ...