Skip to content

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: Prefix Sum + Hash Table

Thinking

The longest subarray with equally many letters and digits. Counting every pair of ends is quadratic.

Letters as \(+1\) and digits as \(-1\) turn the task into the longest zero-sum subarray, i.e. the farthest pair of equal prefix sums.

\(vis\) stores the first index of each prefix, including \(0\mapsto -1\). A repeat of \(s\) yields a zero-sum \((j,i]\); keep the first index so the span is longest.

The problem requires finding the longest subarray with an equal number of characters and digits. We can treat characters as \(1\) and digits as \(-1\), transforming the problem into finding the longest subarray with a sum of \(0\).

We can use the idea of prefix sums and a hash table vis to record the first occurrence of each prefix sum. We use variables mx and k to record the length and the left endpoint of the longest subarray that meets the conditions, respectively.

Next, we iterate through the array, calculating the prefix sum s at the current position i:

  • If the prefix sum s at the current position exists in the hash table vis, we denote the first occurrence of s as j, then the sum of the subarray in the interval \([j + 1,..,i]\) is \(0\). If the length of the current subarray is greater than the length of the longest subarray found so far, i.e., \(mx < i - j\), we update mx = i - j and k = j + 1.
  • Otherwise, we store the current prefix sum s as the key and the current position i as the value in the hash table vis.

After the iteration, we return the subarray with a left endpoint of k and a length of mx.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func findLongestSubarray(_ array: [String]) -> [String] {
        var vis: [Int: Int] = [0: -1]
        var s = 0, mx = 0, k = 0

        for i in 0..<array.count {
            s += array[i].first!.isLetter ? 1 : -1
            if let j = vis[s] {
                if mx < i - j {
                    mx = i - j
                    k = j + 1
                }
            } else {
                vis[s] = i
            }
        }

        return Array(array[k..<(k + mx)])
    }
}

Comments