March LeetCoding Challenge 2021 — Day 6: Short Encoding of Words

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.

sksaikia/LeetCode

I have posted all the previous problems for the March LeetCoding Challenge 2021. You can check them out.

1. March LeetCoding Challenge — Day 1 — Distribute Candies
2. March LeetCoding Challenge — Day 2— Set Mismatch
3. March LeetCoding Challenge — Day 3 — Missing Number
4. March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists
5. March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree