1562. Find Latest Group of Size M Medium

1/**
2 * [1562] Find Latest Group of Size M
3 *
4 * Given an array arr that represents a permutation of numbers from 1 to n.
5 * You have a binary string of size n that initially has all its bits set to zero. At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1.
6 * You are also given an integer m. Find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1's such that it cannot be extended in either direction.
7 * Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.
8 *  
9 * Example 1:
10 * 
11 * Input: arr = [3,5,1,2,4], m = 1
12 * Output: 4
13 * Explanation: 
14 * Step 1: "00<u>1</u>00", groups: ["1"]
15 * Step 2: "0010<u>1</u>", groups: ["1", "1"]
16 * Step 3: "<u>1</u>0101", groups: ["1", "1", "1"]
17 * Step 4: "1<u>1</u>101", groups: ["111", "1"]
18 * Step 5: "111<u>1</u>1", groups: ["11111"]
19 * The latest step at which there exists a group of size 1 is step 4.
20 * 
21 * Example 2:
22 * 
23 * Input: arr = [3,1,5,4,2], m = 2
24 * Output: -1
25 * Explanation: 
26 * Step 1: "00<u>1</u>00", groups: ["1"]
27 * Step 2: "<u>1</u>0100", groups: ["1", "1"]
28 * Step 3: "1010<u>1</u>", groups: ["1", "1", "1"]
29 * Step 4: "101<u>1</u>1", groups: ["1", "111"]
30 * Step 5: "1<u>1</u>111", groups: ["11111"]
31 * No group of size 2 exists during any step.
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	n == arr.length
37 * 	1 <= m <= n <= 10^5
38 * 	1 <= arr[i] <= n
39 * 	All integers in arr are distinct.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/find-latest-group-of-size-m/
45// discuss: https://leetcode.com/problems/find-latest-group-of-size-m/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn find_latest_step(arr: Vec<i32>, m: i32) -> i32 {
51        0
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_1562() {
63    }
64}
65