Design Compressed String Iterator in Java
A compressed string iterator is a data structure that efficiently traverses compressed strings by encoding consecutive characters and their counts while reducing storage space for repeated strings. It should support basic operations, handle large strings, and handle edge cases.
Example:
Input: x5
Output: xxxxx
Using Hybrid Approach
Algorithm
Step 1: Initialize the object with the compressed string and maintain an index to track position within the string.
Step 2: Create a buffer to hold expanded characters and fill it until it contains at least ten characters or the string is fully processed.
Step 3: Read the next character from the compressed string and gather subsequent digits to determine the repetition count for the character.
Step 4: Add the character to the buffer according to the determined count.
Step 5: Return the next character from the buffer when requested.
Step 6: Check if the buffer has more characters; if not, refill it.
Step 7: Return the character and remove it from the buffer.
Step 8: Check if the buffer is not empty.
Here is an implementation of the design compressed string iterator using a hybrid approach:
FileName:CompressedStringIterator.java
import java.util.LinkedList; import java.util.NoSuchElementException; import java.util.Queue; public class CompressedStringIterator { private Queuebuffer; private String compressedString; private int index; public CompressedStringIterator(String compressedString) { this.compressedString = compressedString; this.index = 0; this.buffer = new LinkedList<>(); fillBuffer(); } private void fillBuffer() { // Fill the buffer with characters until it has at least 10 characters or the compressed string is exhausted while (buffer.size() < 10 && index < compressedString.length()) { char c = compressedString.charAt(index++); // Read the next character StringBuilder countBuilder = new StringBuilder(); // StringBuilder to accumulate digits // Accumulate digits to form the count of the current character while (index < compressedString.length() && Character.isDigit(compressedString.charAt(index))) { countBuilder.append(compressedString.charAt(index++)); } int count = Integer.parseInt(countBuilder.toString()); // Convert accumulated digits to an integer // Add the character to the buffer 'count' times for (int j = 0; j < count; j++) { buffer.offer(c); } } } public char next() { if (!hasNext()) { throw new NoSuchElementException(); } char result = buffer.poll(); if (buffer.isEmpty()) { // If the buffer is empty after polling fillBuffer(); // Refill the buffer } return result; // Return the next character } public boolean hasNext() { return !buffer.isEmpty(); // Check if the buffer is not empty } public static void main(String[] args) { CompressedStringIterator iterator = new CompressedStringIterator("a2b3c1"); while (iterator.hasNext()) { System.out.print(iterator.next()); } } }
Output:
aabbbc
Complexity analysis: The time complexity of the `CompressedStringIterator` is O(n), where n is the length of the compressed string. The space complexity is O(1) for the iterator itself, but the buffer can hold up to O(m) characters, where m is the total number of characters after decompression. The overall space complexity is O(m).
Full Decompression on Initialization Approach
Algorithm
Step 1: Starts with an empty `StringBuilder` to store the decompressed string.
Step 2: Iterates through the compressed string, extracts a character, reads subsequent digits to form a count, converts the count to an integer, and appends the character to the `StringBuilder`.
Step 3: Converts the `StringBuilder` to a string and stores it.
Step 4: Create a method to fetch the next character, check if there are more characters, return the current character, and increment the pointer.
Step 5: Creates a method to verify if more characters are left in the decompressed string.
Here is an implementation of the design compressed string iterator using a full decompression on the Initialization approach:
FileName:CompressedStringIterator1.java
import java.util.NoSuchElementException; public class CompressedStringIterator1 { private String decompressedString; private int index; public CompressedStringIterator1(String compressedString) { StringBuilder sb = new StringBuilder(); int i = 0; // Loop through the compressed string to decompress it while (i < compressedString.length()) { char c = compressedString.charAt(i++); // Get the next character (letter) StringBuilder countBuilder = new StringBuilder(); // StringBuilder to build the count // Build the count by reading subsequent digits while (i < compressedString.length() && Character.isDigit(compressedString.charAt(i))) { countBuilder.append(compressedString.charAt(i++)); } // Convert the count from StringBuilder to an integer int count = Integer.parseInt(countBuilder.toString()); // Append the character 'count' times to the decompressed string for (int j = 0; j < count; j++) { sb.append(c); } } this.decompressedString = sb.toString(); this.index = 0; } // Method to return the next character in the decompressed string public char next() { if (!hasNext()) { throw new NoSuchElementException(); } return decompressedString.charAt(index++); } // Method to check if there are more characters in the decompressed string public boolean hasNext() { return index < decompressedString.length(); } public static void main(String[] args) { CompressedStringIterator1 iterator = new CompressedStringIterator1("a2b3c1"); while (iterator.hasNext()) { System.out.print(iterator.next()); } } }
Output:
aabbbc
Complexity analysis: The time complexity of the above approach is O(N), where N is the length of the decompressed string, and space complexity is O(N), where N is the length of the decompressed string.
On-the-Fly Decompression Approach
Algorithm
Step 1: Store compressed string, set index, and count to 0.
Step 2: Read the first character and count if the string is not empty.
Step 3: Set current character to character at current index, increment index.
Step 4: Throw an exception, save the current character, decrease the count, read the next character, and count if the count reaches 0.
Step 5: Return true if the current count is greater than 0.
Step 6: Retrieve and print the next character while more characters exist.
Here is an implementation of the design compressed string iterator using an on-the-fly decompression approach:
FileName:CompressedStringIterator2.java
import java.util.NoSuchElementException; public class CompressedStringIterator2 { private String compressedString; private int index; private char currentChar; private int currentCount; public CompressedStringIterator2(String compressedString) { this.compressedString = compressedString; this.index = 0; this.currentChar = 0; this.currentCount = 0; if (!compressedString.isEmpty()) { readNext(); } } // Reads the next character and its count from the compressed string private void readNext() { if (index < compressedString.length()) { currentChar = compressedString.charAt(index++); StringBuilder countBuilder = new StringBuilder(); // Build the count by reading digits while (index < compressedString.length() && Character.isDigit(compressedString.charAt(index))) { countBuilder.append(compressedString.charAt(index++)); } currentCount = Integer.parseInt(countBuilder.toString()); } } public char next() { if (!hasNext()) { throw new NoSuchElementException(); } char result = currentChar; currentCount--; if (currentCount == 0) { readNext(); } return result; } // Checks if there are more characters left in the expanded string public boolean hasNext() { return currentCount > 0; // Return true if there are remaining counts of the current character } public static void main(String[] args) { CompressedStringIterator2 iterator = new CompressedStringIterator2("a2b3c1"); while (iterator.hasNext()) { System.out.print(iterator.next()); } } }
Output:
aabbbc
Complexity analysis: The time complexity of the above approach is O(n), where n is the length of the compressed string. It is because processing each character and its count takes a constant amount of time, and each character in the compressed string is processed at most once, and space complexity is O(n), where n is the length of the compressed string since we store the compressed string in memory.