Leetcode 443 | String Compression in C++ | Linear Algorithm | Cpp Interview Problem

In order to solve this problem we need to keep track of a few different things. First, we need a variable len to store the resulting length (our answer). Then, we need to count the duplicates and we do this by iterating the array and using two different indices i and j.

Next, we can set our character in the array – this can be ‘a’, ‘b’ or ‘c’ in the first example, and we increment our length, len.
Furthermore, we now need to compute the difference j – i.

If the result is less then ore equal to 1, we simply set i=j and continue iterating through the rest of the elements. If the difference is greater than 1, it is converted to a string which is then iterated, character by character – and the digits are stored in the chars array, while incrementing the len.

The time complexity is O(N) as we iterate through all characters of the array.
The space complexity is O(1) as we are not using any extra space and the chars array is modified in-place.

0:00 - Problem statement
0:46 - Drawing & Explanation
6:44 - Coding & Implementation
9:41 - Complexity Analysis

Related article on Medium, with full explanation:   / leetcode-443-string-compression-in-c-linea...  

leetcode 443
#cpp #codinginterview #array #vector #proramming #interview #interviewprep