Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Extra Characters in a String (medium)

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", words = ["race", "car"]
    • Expected Output: 7
    • Justification: The string `s

.....

.....

.....

Like the course? Get enrolled and start learning!
L

lestatcheb

· 2 years ago

Looks like submissions are broken on this one,

any submission returns this error "Unknown Error - Check your Input".

Submissions in other tasks works fine

D

Davide Pugliese

· 2 years ago

I am looking into problems to learn Dynamic Programming. I think this was not a good example of a problem that needs such a thing. In my view, the proposed solution is over engineered as you literally need only a counter. If you want to improve this solution you can pass as a parameter to the trie the string and the two pointers (left, right) so you don't create a new string each time.

import java.util.Map;
import java.util.HashMap;
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();  // Representing each character of the alphabet.
    boolean isEnd = false;  // To determine if the current TrieNode marks the end of a word.
}

class Trie { 
    TrieNode root; 

    Trie() {
        root = new TrieNode();
    }

    void insert(String word) {
        var
Show 2 replies
Kyle Alberry

Kyle Alberry

· 2 years ago

# class TrieNode:
#     def __init__(self):
#         self.children = {}  # Represents each character of the alphabet.
#         self.isEnd = False  # To determine if the current TrieNode marks the end of a word.
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insertword(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.isEnd = True

class Solution:
    def minExtraChar(self, s, dictionary):
        # Make the tree
        trie = Trie()

        # Build the tree
        for word in dictionary:
            trie.insertword(word)

        # pointers for current word and extra chars
        curword,extras,c = 0,0,0
L

Lee

· 2 years ago

additionally, key error message I was getting was giving completely incorrect line number.

L

lestatcheb

· 2 years ago

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_the_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.end_of_the_word = True

class Solution:
    def minExtraChar(self, s, words):
        # gen Trie with <words>
        t = Trie()
        for word in words:
            t.insert(word)

        # while left pointer less than the end of the <s>,
        # check all substrings
        l = 0
        found_words_len = 0
        l_need_to_jump = False
        while l < len(s):
            node = t.
Show 1 reply
M

mailman14736

· 20 days ago

Solution checking is incorrect,

input


"keepingkeep"
["keeping", "keep"]

output

Output: 0
Expected: 3

actual expected should be 0, my answer is correct, and the solution in the solution section also gives 0