Google Interview Question— LeetCode 1055

Y Tech

Follow

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²).

Python Implementation

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).

Python Implementation

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.

Python Implementation