String Compression - Leetcode Solution

Problem Statement:

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group's length is 1, append the character to s. Otherwise, append the character followed by the group's length.

The compressed string s should not have adjacent repeating characters. Return the compressed string.

Solution:

The problem can be solved by iterating through the given array of chars and keeping track of the current character and its count. Whenever a new character is encountered, the count of the previous character is appended to the resulting string s along with the character itself. The count is set to 1 for the new character. If a character is encountered again, the count is incremented. After the loop is complete, the last character's count is appended to the resulting string.

Algorithm:

• Initialize an empty string s and set the count variable to 1.
• Iterate through the characters of the given array, starting from the second character.
• If the current character is the same as the previous character, increment count.
• If the current character is different from the previous character, append the previous character and its count to s and set the count variable to 1.
• After the loop, append the last character and its count to s.
• Return the resulting string s.

Pseudo Code:

s = "" count = 1 for i in range(1, len(chars)): if chars[i] == chars[i-1]: count += 1 else: s += chars[i-1] + str(count) count = 1 s += chars[-1] + str(count) return s

Time Complexity:

The time complexity of the solution is O(n) as we are iterating through each character of the given array once.

Space Complexity:

The space complexity of the solution is O(1) as we are not using any extra space apart from the resulting string s and the count variable.

Code:

class Solution: def compress(self, chars: List[str]) -> int: s = "" count = 1 for i in range(1, len(chars)): if chars[i] == chars[i-1]: count += 1 else: s += chars[i-1] + str(count) count = 1 s += chars[-1] + str(count) chars[:] = list(s) return len(chars)

1