Grokking Data Structures & Algorithms for Coding Interviews

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!
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