# Google Interview Question— LeetCode 1055

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`

:

- 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`

; - 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`

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

.