Extra Characters in a String

Extra Characters in a String is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Tries subpattern.

Problem statement

Given a string s and a collection of distinct words in dictionary, split s into consecutive, non-overlapping pieces. A piece that exactly matches a word in dictionary contributes no extra characters; every other character contributes one extra character. Dictionary words may be used wherever they match, including more than once.

The order of characters in s cannot change, and every character must belong to exactly one chosen piece. Return the smallest possible number of extra characters after choosing the best valid collection of dictionary-word matches.

Implement Solution.minExtraChar(self, s: str, dictionary: List[str]) -> int and return that minimum as an integer.

Example 1:

Input: s = "blueberry", dictionary = ["blue","berry","red"] Output: 0 Explanation: Use "blue" for the first four characters and "berry" for the remaining five. Every character is covered by a dictionary word, so the number of extra characters is 0.

Example 2:

Input: s = "caterpillar", dictionary = ["cat","art","pillar"] Output: 2 Explanation: Use "cat" for the first three characters and "pillar" for the final six characters. The two characters between them, "er", are not covered by a dictionary word, so both count as extra.

Example 3:

Input: s = "qwerty", dictionary = ["we","ert"] Output: 3 Explanation: Using "ert" covers the third through fifth characters, leaving "q", "w", and "y" extra. Alternatively, using "we" leaves "q", "r", "t", and "y" extra, so the better choice has 3 extra characters.

Constraints:

- 1 <= len(s) <= 50 - 1 <= len(dictionary) <= 1000 - 1 <= len(dictionary[i]) <= 50 - s and every dictionary word contain only lowercase English letters - dictionary contains distinct words

Topics and companies

Topics: Dynamic Programming, Trie, String.

How to practise Extra Characters in a String on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * d * L), where n is the length of s, d is the number of dictionary words, and L is the maximum dictionary-word length. time and O(n) auxiliary space. space.

Open Extra Characters in a String in the code editor, or read the Extra Characters in a String editorial for a worked solution with its approach and complexity analysis.

Where Extra Characters in a String sits in the DSA pattern sheet

Problems related to Extra Characters in a String

Other problems that use the same Tries and Design Patterns techniques:

Preparing this workspace.