Today, we will solve the 6th problem of the March LeetCoding Challenge.
Problem Statement
A valid encoding of an array of words is any reference string s and an array of indices indices such that:
words.length == indices.length
The reference string s ends with the '#' character.
For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].
Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.
Example 1:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"
Example 2:
Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].
Constraints:
1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i] consists of only lowercase letters.
Solution
According to the question, we have to encode the given strings into one string that contains all the words from the given array of strings. It should be done in such a way that, we can minimize the length of the output string. Overlapping a string over another is allowed. Also after each string, we have to append # to it.
Let's go through the algorithm for this problem. Here we have used a Hashset to save all the given strings. We will check for overlapping of characters of words, if there is any overlapping of characters we delete that string. (This step can be better understood with the example). At last, we append the strings present in the Hashset and add # to it.
The code is given below.
If n is the length of the array of strings and k is the length of the longest string then
Time complexity: O(n*k)
Space complexity: O(n)
The code can be found in the following repository.
I have posted all the previous problems for the March LeetCoding Challenge 2021. You can check them out.
Top comments (0)