Google Interview Question— LeetCode 1055

Y Tech
Y Tech
Aug 3, 2020 · 3 min read

In this blog, we will discuss an interview question asked by Google.

In this post, we are going to discuss the leetcode problem no. 1055 — Shortest Way to Form String, which is recently asked in Google interviews.

Firstly, we will try to solve the problem with brute force method in O(n²) running time; then we will improve our algorithm to O(n log n) running time; finally we will further improve the algorithm to O(n).

Problem Analysis

The input of the problem is two strings: source and target. The expected output is the minimum number of subsequences of source to form the target.

For example, we can have source as 'abcd’, and target as 'aabacb’. Then the output will be 4, as we need at least the following subsequences of the source to form the target: 'a’, 'ab’, 'ac’, and 'b’.

Brute Force — O(n²)

The most intuitive implementation of the problem is, we can define a starting index i for string source, with an initialized value of 0. Then we loop through each character in the target:

  1. If the character exists in source after position i (e.g. exists at position j where j>i), we move on to the next character, and set i to the value of j;
  2. If the character does not exists in source after position i, and i is 0, we return -1 as we cannot form target by using source.
  3. If the character does not exists in source after position i, and i is not 0, we increment the output count by 1, and set i to 0, and then repeat from step 1.

With this algorithm, we will basically have a nested loop, first level of the loop is the looping over string target, and second level of the loop is looping over the string source to check the existence and position of the character. So the running time will be O(n²).

Binary Search — O(n log n)

We can improve the second loop from O(n) to O(log n) by memorizing the positions of each character in the source, and using binary search for step 1 in the Brute Force Algorithm.

For example, if the source is 'abcabba', we can build a map to save the character positions as: {'a': [0, 3, 6], 'b': [1, 4, 5], 'c': [2]}. By using this map, we can do binary search when we try to find a character after position i, and it will improve our running time to O(n log n).

Improved Method — O(n)

If we assume copy an object takes O(1), then we can further improve the algorithm in linear time O(n). For each position i in source, we can memorize the first appearance of the characters after position i.

For example, if the source is 'abcabba', we can build a map to save the character positions as: {0: {'b': 1, 'a': 0, 'c': 2}, 1: {'b': 1, 'a': 3, 'c': 2}, 2: {'b': 4, 'a': 3, 'c': 2}, 3: {'b': 4, 'a': 3}, 4: {'b': 4, 'a': 6}, 5: {'b': 5, 'a': 6}, 6: {'a': 6}}.

With this map, assume we are currently at index 2 (e.g. i=2), and our character to search is 'a', so we can get map[2]['a'] is 3, which means the first 'a' after index 2 is at position 3; and then for the next character, we need to start search at 4, which means we need to set i to 4.

The Startup

Medium's largest active publication, followed by +773K people. Follow to join our community.

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