面试题 17.05

Given an array filled with letters and numbers, find the longest subarray with an equal number of letters and numbers.

Return the subarray. If there are more than one answer, return the one which has the smallest index of its left endpoint. If there is no answer, return an empty arrary.

Example 1:

Input: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

Output: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"] Example 2:

Input: ["A","A"]

Output: [] Note:

array.length <= 100000

Solutions

1. prefixsum and hashmap O(n)

2. The number of characters or numbers in array(i:j] can be calculated in O(1) time based on the prefix countsum of array[:i] and array[:j].

class Solution {
public:

    vector<string> findLongestSubarray(vector<string>& array) {
        int n = array.size();
        // m stores the index of the first appearance of a certain `n_num - n_char`
        unordered_map<int, int> m;
        m[0] = -1;
        // donot explicitly record the number of characters/numbers respectively.
        // only their count diffference matters.
        int diff = 0, maxlen = 0, minst = 0;
        for (int i = 0; i < n; i++) {
            diff += isdigit(array[i][0]) ? 1 : -1;
            if (!m.count(diff))
                m[diff] = i;
            else if (i - m[diff] > maxlen || m[diff] + 1 < minst) {
                minst = m[diff] + 1;
                maxlen = i - m[diff];
            }
        }

        return {array.begin() + minst, array.begin() + minst + maxlen};
    }
};