443. String Compression

use hashmap

T: O(n)

S: O(n)

use two pointers

T: O(n), 
S: O(1)
class Solution {
    public int compress(char[] chars) {
        int n = chars.length;
        
        int newIdx = 0;
        
        int right = 0; // 經典的同向雙指針
        int left = 0;
        while (right < n) {
            
            char c = chars[left];
            while (right < n && chars[left] == chars[right]) {
                right++;
            }
            int freq = right - left;
            
            // 1. append this letter
            chars[newIdx++] = c;
            // 2. if count != 1, need append count char (12 => "1", "2")
            if (freq != 1) { 
                for (char countChar : String.valueOf(freq).toCharArray()) {
                    chars[newIdx++] = countChar;
                }
            }
            
            left = right;
        }
        
        return newIdx; // newIdx, at last will be the length (newIdx++ one more time)
    }
}

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

abb

ab2

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

ab12

solution: T: O(n), S: O(1)
use two pointers to get freq count

this q, chars also needs modifying:
After you are done modifying the input array, return the new length of the array.

["a","a","b","b","c","c","c"]
  i.      j
          i
  1. append this letter
  2. if count != 1, need append count char (12 => "1", "2")
  
  
*/

类似丝丝叁,但要求 in place,长度为1也记录进去,如果压缩后长度大于原字符串,返回error。
当场紧张这点没想明白怎么做。
比如
"aaa" -> "3a",能压缩
"abc" -> "1a1b1c", 不能压缩
"abbb" -> "a1b3", 能压缩

class Solution {
    public int compress(char[] chars) {
        int n = chars.length;
        
        int newIdx = 0;
        
        int right = 0; // 經典的同向雙指針
        int left = 0;
        while (right < n) {
            
            char c = chars[left];
            while (right < n && chars[left] == chars[right]) {
                right++;
            }
            int freq = right - left;
            
            try {
                // 1. append this letter
                chars[newIdx++] = c;
                // 2. append count
                for (char countChar : String.valueOf(freq).toCharArray()) {
                    chars[newIdx++] = countChar;
                }
            } catch (Exception e) {
                throw new RuntimeException("illegal compressed");
            }
            
            left = right;
        }
        
        return newIdx; // newIdx, at last will be the length (newIdx++ one more time)
    }
}

Last updated

Was this helpful?