# 面试题 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]`.

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