README_EN.md

17.05. Find Longest Subarray

中文文档

Description

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

Python3

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        seen = {0: -1}
        t = mx = 0
        ans = []
        for i, s in enumerate(array):
            t += 1 if s.isalpha() else -1
            if t in seen:
                if mx < i - seen[t]:
                    mx = i - seen[t]
                    ans = array[seen[t] + 1: i + 1]
            else:
                seen[t] = i
        return ans

Java

class Solution {
    public String[] findLongestSubarray(String[] array) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, -1);
        int t = 0, mx = 0;
        int j = 0;
        for (int i = 0; i < array.length; ++i) {
            t += Character.isDigit(array[i].charAt(0)) ? 1 : -1;
            if (seen.containsKey(t)) {
                if (mx < i - seen.get(t)) {
                    mx = i - seen.get(t);
                    j = seen.get(t) + 1;
                }
            } else {
                seen.put(t, i);
            }
        }
        String[] ans = new String[mx];
        for (int i = 0; i < mx; ++i) {
            ans[i] = array[i + j];
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        unordered_map<int, int> seen;
        seen[0] = -1;
        int t = 0, mx = 0, j = 0;
        for (int i = 0; i < array.size(); ++i)
        {
            t += isdigit(array[i][0]) ? 1 : -1;
            if (seen.count(t))
            {
                if (mx < i - seen[t])
                {
                    mx = i - seen[t];
                    j = seen[t] + 1;
                }
            }
            else
            {
                seen[t] = i;
            }
        }
        return {array.begin() + j, array.begin() + j + mx};
    }
};

Go

func findLongestSubarray(array []string) []string {
	seen := map[int]int{0: -1}
	t, mx, j := 0, 0, 0
	for i, s := range array {
		if unicode.IsDigit(rune(s[0])) {
			t++
		} else {
			t--
		}
		if k, ok := seen[t]; ok {
			if mx < i-k {
				mx = i - k
				j = k + 1
			}
		} else {
			seen[t] = i
		}
	}
	return array[j : j+mx]
}

...