String Compression

Compress a string by encoding consecutive character sequences into character-count pairs

Understand the Problem

Problem Statement

String Compression: Given a string S, compress the string by encoding consecutive character sequences as character-count pairs.
Example 1:
Input:
aaabbbbcc
Output:
a3b4c2

Example 2:
Input:
abc
Output:
a1b1c1

Constraints

String length: 1 ≤ |S| ≤ 10,000
String contains only lowercase English letters (a-z)
Input string will not be empty
Output should maintain the order of characters as they appear

Examples

Example 1

Input

aaabbbbcc

Output

a3b4c2

Explanation

The string has 3 consecutive 'a's, followed by 4 consecutive 'b's, followed by 2 consecutive 'c's. The output is formatted as character-count pairs: a3b4c2.

Example 2

Input

abc

Output

a1b1c1

Explanation

Each character appears only once consecutively, so each gets a count of 1. The output shows each character with its count: a1b1c1.

Solution

#include <stdio.h>
#include <string.h>

int main() {
    char arr[10001];
    int count = 1;
    
    // Read input string
    scanf("%s", arr);
    
    int length = strlen(arr);
    
    // Process consecutive characters
    for (int i = 0; i < length; i++) {
        // If current character is same as next character
        if (i < length - 1 && arr[i] == arr[i + 1]) {
            count++;
        } else {
            // Different character or end of string
            printf("%c%d", arr[i], count);
            count = 1;  // Reset counter for next character
        }
    }
    
    return 0;
}

Time:O(n) where n is the length of the input string

Space:O(1) excluding the input string storage

Approach:

The C solution reads the input string into a character array. It uses a single loop to traverse the string, comparing each character with the next one. When characters match, it increments a counter. When a different character is found or when reaching the end of the string, it prints the current character and its count, then resets the counter for the next sequence.

Key aspects:

Uses strlen() to get string length
Bounds checking with i < length - 1 prevents out-of-bounds access
Counter starts at 1 since each character appears at least once
Output format is character followed by count using %c%d in printf

Visual Explanation

Loading diagram...

All Problems