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

Sourav Saikia
Mar 7 · 2 min read

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:

Example 2:

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)

LeetCode Simplified

Learn to Solve Leetcode Problems and Get Offers From Your Dream Companies

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store