Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. String

String Compression

String, Iterative approach

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

Solutions

Approach - Copy characters to new String

At first glance, implementing this method seems fairly straightforward, but perhaps a bit tedious. We iterate through the string, copying characters to a new string and counting the repeats. At each iteration, check if the current character is the same as the next character. If not, add its compressed version to the result.

Steps

  1. First check if string is null, then return string.

  2. Create a new empty string to store the characters.

  3. Create character counter variable.

  4. Run loop over the length of string and increment character count. Check if current character is not same a next one then, add current character into result string and also check if current string counter value is greater than one, then add counter value also into result string. Now, reset counter to zero.

  5. Return new string.

    public string Compress(string str)
    {
        if (str is null)
            return str;

        string final = "";

        int count = 0;
        for (int i = 0; i < str.Length; i++)
        {
            count++;
            if (i + 1 >= str.Length || str[i] != str[i + 1])
            {
                final += str[i + 1 >= str.Length ? str.Length - 1 : i];

                if (count > 1)
                    final += count;
                count = 0;

            }

        }

        return final;
    }

Complexity

  • Time Complexity: O(n + k²)

  • Auxiliary Space: O(n)

The runtime is O(n + k²), where n is the size of the original string and k is the number of character sequences. For example, if the string is aabccdeeaa, then there are six charactes sequences. It's slow because string concatenation operates in O(n²) time. We can fix this by using a StringBuilder.

Approach - Copy characters to StringBuilder


Steps

  1. First check if string is null, then return string.

  2. Create a new StringBuilder instance to store the characters.

  3. Create character counter variable.

  4. Run loop over the length of string and increment character count. Check if current character is not same a next one then, add current character into result StringBuilder and also check if current string counter value is greater than one, then add counter value also into result StringBuilder. Now, reset counter to zero.

  5. Return new string.

public string Compress(string str)
    {
        if (str is null)
            return str;

        StringBuilder sb = new StringBuilder(str.Length / 2);

        int count = 0;
        for (int i = 0; i < str.Length; i++)
        {
            count++;
            if (i + 1 >= str.Length || str[i] != str[i + 1])
            {
                sb.Append(str[i + 1 >= str.Length ? str.Length - 1 : i]);
                if (count > 1)
                    sb.Append(count);
                count = 0;

            }
        }

        return sb.ToString();
    }

Complexity

  • Time Complexity: O(n)

  • Auxiliary Space: O(n)

PreviousCheck if two strings are permutation of each otherNextPalindrome Permutation

Last updated 1 year ago