# COMPRESSVD Editorial

Setter: Kanhaiya Mohan
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

940

None

# PROBLEM:

Chef recorded a video explaining his favorite recipe. However, the size of the video is too large to upload on the internet. He wants to compress the video so that it has the minimum size possible.

Chef’s video has N frames initially. The value of the i^{th} frame is A_i. Chef decides to remove a frame only if its value is equal to the value of either of its neighbors.

Find the minimum number of frames Chef can achieve.

# EXPLANATION:

Basically in this problem we need to calculate the total number of substrings having same characters. Here the video is considered as a string with each frame as individual character.

Initially we start with n frames. On traversing the string whenever we find two adjacent frames as equal, we can decrement our frames by 1, since those two frames would belong to the same substring.
After traversing we would get the final answer as frames.

# TIME COMPLEXITY:

O(N), for each test case.