Question

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"

Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"

Constraints:

• s.length == indices.length == n
• 1 <= n <= 100
• s contains only lower-case English letters.
• 0 <= indices[i] < n
• All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

Idea

First Thought

I can come up with a simple solution immediately, that is to create a new string with same length as original one, and then map all characters from original string based on the indices.

class Solution {
public:
  string restoreString(string s, vector<int> &indices) {
    string ret;
    ret.resize(s.size());
    for (int i = 0; i < indices.size(); ++i) {
      ret[indices[i]] = s[i];
    }
    return ret;
  }
};

The execution time is 16ms (73.18%), and memory usage is 15.5MB (30.16%). To be honest, it is not a bad solution in terms of the execution time. However, the memory usage is a little poor. We’re using non-in-place algorithm here, and fairly speaking, that is the least memory usage for a non-in-place solution. If we want to improve the memory usage, we must use an inplace solution, epecially when the first argument of the function is a copy of original string s.

In-Place Solution

An in-place solution must guarantee that when we map an element to a new place, the element at the new place must be mapped right next; otherwise, we will lose the element.

Let’s take a look at the first example. When we process the first element c, it should be mapped to the 4th slot. Therefore, we replace the 4th element l with c. Now we need to process the l immediately, so it should go to the first slot, and we replace the first element with l. But what now? We’re back to the start point. Are we going to do it again? Of course not, because we would be stuck in an infinite loop. We need somehow to tell we’ve already processed a specific element.

Here is the trick. When mapping an element to its new place, instead of just replace the element at new place, we swap them. Then the element at new place goes to the old place. Recall that elements in indices represent that the ith element should be mapped to indices[i]th slot. After the swap, the indices[i]th element is swapped to ith slot. If we also swap ith and indices[i]th element in indices, we can keep this relation unchanged. Let’s still use the first example. After the swap, s becomes lodeceet, and indicesbecomes [0,5,6,7,4,2,1,3]. Now if we look at the indices, basically it says the first element goes to the first slot, which means we have already reach an end here. Everytime we do a swap, the starting point reaches to its final position, which means i == indices[i]. Therefore, we can take i == indices[i] as a condition to stop. That’s the essence of cyclic sort, that is everytime we find a right position for a specific element.

Solution

class Solution {
public:
  string restoreString(string s, vector<int> &indices) {
    for (int i = 0; i < indices.size(); i++) {
      while (indices[i] != i) {
        swap(s[i], s[indices[i]]);
        swap(indices[i], indices[indices[i]]);
      }
    }

    return s;
  }
};

Runtime: 12 ms, faster than 91.66% of C++ online submissions for Shuffle String. Memory Usage: 15.2 MB, less than 93.44% of C++ online submissions for Shuffle String.

Question

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”

Output: 3

Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”

Output: 1

Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”

Output: 3

Explanation: The answer is “wke”, with the length of 3.

Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Idea

The most intuitive way is to save each character and its index into a map. Every time it encounters a repeating character, let’s say c, remove all characters before c and their indices from the map. Besides, the max length should also be stored and updated accordingly. Well, it does work, but not perfectly. The only reason is we operate each character twice. In the worst case, the time complexity is O(n^2).

So do we really need to check whether a character is in the map so that we could know that whether the character is repeating? Let’s change our mind a little bit. Our previous thought is to check the map to see whether the character is in the substring. That’s why we need to remove all characters that are not in the substring from the map. What if we set a variable s representating the start of substring? In this way, as long as the index is less than s, the corresponding character is not in the substring. We don’t need to perform deletion any more. We only check each character once!

Solution

class Solution {
private:
  int quick_max(int x, int y) { return x ^ ((x ^ y) & -(x < y)); }
public:
  int lengthOfLongestSubstring(string s) {
    vector<int> map(256, -1);
    auto max_len = 0, start = -1;
    for (int i = 0; i < s.size(); ++i) {
      if (map[s[i]] > start) {
        start = map[s[i]];
      }
      map[s[i]] = i;
      max_len = quick_max(max_len, i - start);
    }
    return max_len;
  }
};

There’s a tricky function quick_max to compare two integers and return the larger one. It is bitwise operation. std::max uses conditional statement which impacts pipeline very much. I generally avoid using conditional statement as much as possible to gain better performance. In this case, the comparison happens in every iteration, we do need to use a much more efficient way to make it. This small change greatly improves performance. The running time decreases from 16ms to 8ms. 1X speedup!

From now on, I’d like to solve all algorithm questions on Leetcode one by one to help me pass the job hunting interview in the future, no matter for internship or regular job. 🙂 I also pushed my solution on GitHub.

Let’s get started from the first question: Two Sum.

Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9, because nums[0]+nums[1] =2+7=9, return [0, 1].

Idea

The main thought is to traverse the whole vector. For each element, check whether the subtrahend exists in the vector. If yes, then return indices of current element and subtrahend. As a result, we need to maintain a structure that could provide us both the value and its index with a good performance. std::unordered_mapis a best choice here.

We’ve not considered another case where the subtrahend doesn’t exist for the moment. What should we do? Think about it, for example, a + b = c where c is our target. Now we get a and check whether b exists. It doesn’t. In order to let us find a when we reach b, we should store a and its index. That’s it. In this way, we can outline the whole traverse.

Solution

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> map;
    for (auto i = 0; i < nums.size(); ++i) {
      const auto key = target - nums[i];
      if (map.find(key) != map.end()) {
        return vector<int>({i, map[key]});
      }
      map[nums[i]] = i;
    }
    return vector<int>();
  }
};

Runtime: 4 ms, faster than 99.70% of C++ online submissions for Two Sum. Memory Usage: 10.1 MB, less than 55.86% of C++ online submissions for Two Sum.

Digression

Three years and four months ago, I submitted a solution with same idea but different code. Its running time is 16ms. Wow. Totally identical idea! This could demonstrate how important writing code efficiently. 🙂 Here is the old solution:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        if (nums.size() == 0) {
            return ret;
        }
        unordered_map<int, size_t> hash;
        for (int i = 0; i < nums.size(); ++i) {
            int left = target - nums[i];
            if (hash.find(left) != hash.end()) {
                ret.push_back(i);
                ret.push_back(hash[left]);
                return ret;
            } else {
                hash[nums[i]] = i;
            }
        }
        return ret;
    }
};