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

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:

`Input: words = ["time", "me", "bell"]Output: 10Explanation: 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: 2Explanation: 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)

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

## LeetCode Simplified

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

## LeetCode Simplified

We are going to solve Leetcode problems live, which you can watch on our youtube channel

Written by

## Sourav Saikia

Tech-enthusiastic . Connect me — https://twitter.com/sourav__saikia

## LeetCode Simplified

We are going to solve Leetcode problems live, which you can watch on our youtube channel

## Designing Secure Data Pipelines with VPC Service Controls

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