[Algorithm] Longest Repeating Subarray after K Updates(Array/C++)

Link: https://binarysearch.com/problems/Longest-Repeating-Sublist-After-K-Updates

Hello! Today we’ll be looking at an array question. You’re given one operation which is to change any element in the array to any value. Then, you need to perform K operations to create the longest repeating subarray. Keep in mind that “subarray” is contiguous while “subsequence” doesn’t have to be adjacent to each other.

This question is categorized as “easy” but might seem quite tricky to come up with a solution. Let me take an example test case. If we have [7,5,5,3,2,5,5], we can change [3] and [2] to [5] so that we have [7,5,5,5,5,5,5] whose LRS’s length is 6.

A valid approach is to use sliding-window. We try if it’s possible to form a subarray with size X. Then, we maintain the window size as X and traverse through the array. Here, we keep tracking of the frequency in the hash map. When the frequency of any variable in the current window + K≥ X, then it’s possible to flip those remaining K elements and make the current subarray a repeating subarray with a size X. For example, if we have [7,5,5,3,2] and our desired window size is 4, we can make a repeating subarray with size 4 from [7,5,5,3] since we have two 5’s.

Instead of linearly increasing window size, binary search can be used to enhance time complexity.