Question

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

Solution 1

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

class Solution {
  public String[] findLongestSubarray(String[] array) {
    Map<Integer, Integer> vis = new HashMap<>();
    vis.put(0, -1);
    int s = 0, mx = 0, k = 0;
    for (int i = 0; i < array.length; ++i) {
      s += array[i].charAt(0) >= 'A' ? 1 : -1;
      if (vis.containsKey(s)) {
        int j = vis.get(s);
        if (mx < i - j) {
          mx = i - j;
          k = j + 1;
        }
      } else {
        vis.put(s, i);
      }
    }
    String[] ans = new String[mx];
    System.arraycopy(array, k, ans, 0, mx);
    return ans;
  }
}

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

func findLongestSubarray(array []string) []string {
  vis := map[int]int{0: -1}
  var s, mx, k int
  for i, x := range array {
    if x[0] >= 'A' {
      s++
    } else {
      s--
    }
    if j, ok := vis[s]; ok {
      if mx < i-j {
        mx = i - j
        k = j + 1
      }
    } else {
      vis[s] = i
    }
  }
  return array[k : k+mx]
}

function findLongestSubarray(array: string[]): string[] {
  const vis = new Map();
  vis.set(0, -1);
  let s = 0,
    mx = 0,
    k = 0;
  for (let i = 0; i < array.length; ++i) {
    s += array[i] >= 'A' ? 1 : -1;
    if (vis.has(s)) {
      const j = vis.get(s);
      if (mx < i - j) {
        mx = i - j;
        k = j + 1;
      }
    } else {
      vis.set(s, i);
    }
  }
  return array.slice(k, k + mx);
}