ข้อ 9 · LC443 String Compression 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

ย่อกลุ่มตัวอักษรซ้ำติดกันใน chars แบบ in-place (เช่น a,a,b,b,c,c,c → a,2,b,2,c,3) แล้วคืนความยาวใหม่

ให้ลิสต์ของตัวอักษรชื่อ chars โดยหนึ่งช่องเก็บได้หนึ่งตัวอักษร จงย่อมันให้สั้นลง

วิธีย่อคือมองหาตัวอักษรเดิมที่ซ้ำกันและอยู่ติดกันเป็นกลุ่ม แล้วเขียนแทนกลุ่มนั้นด้วยตัวอักษรหนึ่งตัวตามด้วยจำนวนที่นับได้ ถ้ากลุ่มไหนมีแค่ตัวเดียว ให้เขียนแค่ตัวอักษร ไม่ต้องเขียนเลข 1

ต้องแก้ลงใน chars เดิม ห้ามสร้างลิสต์ใหม่มาช่วย และ return ความยาวใหม่ ไม่ใช่ return ลิสต์

ถ้าจำนวนที่นับได้มีหลายหลัก เช่น 12 ต้องแยกลงสองช่อง ช่องหนึ่งเก็บ "1" อีกช่องเก็บ "2"

Example 1

Input:: chars = ["a","a","b","b","c","c","c"]
Output:: 6, chars 6 ช่องแรกกลายเป็น ["a","2","b","2","c","3"]
Explanation:: กลุ่ม a ยาว 2 → a2, กลุ่ม b ยาว 2 → b2, กลุ่ม c ยาว 3 → c3 ต่อกันได้ a2b2c3 ยาว 6 ช่อง

Example 2

Input:: chars = ["a"]
Output:: 1, chars = ["a"]
Explanation:: กลุ่มเดียวและยาวแค่ 1 จึงเขียนแค่ "a" ห้ามเขียน "a1"

Example 3

Input:: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output:: 4, chars 4 ช่องแรกกลายเป็น ["a","b","1","2"]
Explanation:: กลุ่ม a ยาว 1 → เขียนแค่ "a" ส่วนกลุ่ม b ยาว 12 → เขียน "b" แล้วแตกเลข 12 ลงสองช่องเป็น "1" และ "2"

Constraints (ข้อจำกัด)

1 <= chars.length <= 2000
chars[i] เป็นตัวอักษรพิมพ์เล็ก พิมพ์ใหญ่ หรือตัวเลข 0-9
ต้องแก้ใน chars เอง และใช้พื้นที่เพิ่มแค่ O(1)

⏸ ลองเองก่อน 25 นาที

ข้อนี้เป็นข้อปิดหมวดและรวมทุกอย่างที่เรียนมา ถ้ายังไม่มั่นใจ แนะนำให้ทำข้ออื่นให้ครบก่อนแล้วกลับมา เพราะมันต้องเขียนทับลิสต์เดิมระหว่างที่ยังอ่านไม่จบ ซึ่งฟังดูเหมือนทำไม่ได้

💡 ใบ้ขั้นที่ 1 — แยกสองหน้าที่ออกจากกัน

งานของข้อนี้มีสองหน้าที่ที่เดินคนละจังหวะ คือ อ่านของเดิม กับ เขียนผลลัพธ์

ถ้าใช้ตัวแปรตัวเดียวคุมทั้งสองหน้าที่จะสับสนแน่ ให้ใช้สองตัวแยกกัน เรียกว่า read กับ write

💡 ใบ้ขั้นที่ 2 — จังหวะการเดินของแต่ละตัว

read เดินไปข้างหน้าเพื่อนับว่ากลุ่มนี้ยาวเท่าไหร่ พอนับจบก็จะไปหยุดที่หัวกลุ่มถัดไปพอดี

write ขยับเฉพาะตอนที่เขียนของลงไปจริง ซึ่งจะช้ากว่า read เสมอเมื่อมีการบีบอัด

💡 ใบ้ขั้นที่ 3 — โครงทั้งหมด

python

write = read = 0
n = len(chars)
while read < n:
    ch = chars[read]
    count = 0
    while read < n and chars[read] == ch:    # นับกลุ่มนี้ให้จบก่อน
        read += 1
        count += 1
    chars[write] = ch
    write += 1
    if count > ___:                          # เขียนเลขเมื่อไหร่
        for d in ___(count):                 # เลขหลายหลักต้องแตกทีละตัว
            chars[write] = d
            write += 1
return write

🧭 กล่องสอน — ไล่ตั้งแต่ศูนย์ทีละขั้น (เปิดเมื่อพร้อม)

ขั้นที่ 1 · โจทย์นี้ขออะไรจริง ๆ

สิ่งแรกที่ต้องสังเกตคือ โจทย์ให้ chars เป็น ลิสต์ของตัวอักษร ไม่ใช่ string ซึ่งไม่ใช่เรื่องบังเอิญ

เพราะโจทย์บังคับให้แก้ในที่เดิม และ string ในภาษาส่วนใหญ่แก้ในที่เดิมไม่ได้ (ย้อนไปดูส่วนที่ 1 ของหน้าแนวคิด) จึงต้องใช้ลิสต์

อย่างที่สองคือ return ความยาวใหม่ ไม่ใช่ลิสต์ แปลว่าของที่ค้างอยู่ท้ายลิสต์หลังตำแหน่งนั้นไม่มีใครสนใจ เราไม่ต้องล้างให้สะอาด

ขั้นที่ 2 · ปัญหาที่ดูเหมือนทำไม่ได้

ความยากอยู่ที่เราต้องเขียนผลลัพธ์ลงในลิสต์เดียวกับที่ยังอ่านไม่จบ ฟังดูเหมือนต้องทับข้อมูลที่ยังไม่ได้อ่านแน่ ๆ

ทางออกคือใช้ตัวชี้สองตัวเดินคนละจังหวะ ให้นึกภาพคนคัดของที่ใช้สองมือ

มือขวาคือ read หยิบของขึ้นมาดูทีละชิ้นและเดินไปข้างหน้าเรื่อย ๆ · มือซ้ายคือ write คอยวางของที่ย่อแล้วลงในแถวเดิมจากช่องแรก

เพราะของที่ย่อแล้วมีจำนวนน้อยกว่าหรือเท่ากับของที่ดูไปแล้ว มือซ้ายจึงเดินช้ากว่ามือขวาเสมอ และไม่มีทางไปวางทับของที่ยังไม่ได้หยิบ

ขั้นที่ 3 · เดินตามโค้ดทีละสเต็ป

โค้ดข้างล่างพิมพ์ค่า write กับ read ทุกกลุ่ม ให้ดูคอลัมน์สุดท้ายที่ยืนยันว่า write ไม่เคยแซง read

ไล่ทีละกลุ่ม พร้อมเช็คว่า write ไม่เคยแซง readpython

chars = ["a","a","b","b","c","c","c"]
write = read = 0
n = len(chars)
while read < n:
    ch = chars[read]
    count = 0
    while read < n and chars[read] == ch:
        read += 1; count += 1
    print(f"  กลุ่ม {ch!r} ยาว {count} (read เดินถึง {read})")
    chars[write] = ch; write += 1
    if count > 1:
        for d in str(count):
            chars[write] = d; write += 1
    print(f"     เขียนแล้ว -> {chars[:write]} | write={write} read={read} | write<=read? {write<=read}")
print("ความยาวใหม่ =", write, "| ผลลัพธ์ =", chars[:write])

Output

  กลุ่ม 'a' ยาว 2 (read เดินถึง 2)
     เขียนแล้ว -> ['a', '2'] | write=2 read=2 | write<=read? True
  กลุ่ม 'b' ยาว 2 (read เดินถึง 4)
     เขียนแล้ว -> ['a', '2', 'b', '2'] | write=4 read=4 | write<=read? True
  กลุ่ม 'c' ยาว 3 (read เดินถึง 7)
     เขียนแล้ว -> ['a', '2', 'b', '2', 'c', '3'] | write=6 read=7 | write<=read? True
ความยาวใหม่ = 6 | ผลลัพธ์ = ['a', '2', 'b', '2', 'c', '3']

สังเกตสองกลุ่มแรก write เท่ากับ read พอดี เพราะกลุ่มยาว 2 เขียนเป็น a2 ก็ใช้ 2 ช่องเท่าเดิม ไม่ได้ประหยัดแต่ก็ไม่ล้น

กลุ่มที่สามยาว 3 เขียนเป็น c3 ใช้แค่ 2 ช่อง ตรงนี้จึงเริ่มประหยัดจริง และ write ตามหลัง read ห่างขึ้น

เหตุผลที่รับประกันว่าปลอดภัยทุกกรณี

ผลลัพธ์ของกลุ่มยาว k ตัวไม่เคยกินที่เกิน k ช่อง ไล่ดูได้: k=1 เขียนตัวอักษรเดียวใช้ 1 ช่อง · k=2 เขียน a2 ใช้ 2 ช่อง · k ตั้งแต่ 3 ขึ้นไปเขียนสั้นกว่า k เสมอ และเราเขียนหลังจาก read เดินผ่านกลุ่มนั้นจบแล้ว จึงทับได้แค่ช่องที่อ่านไปแล้ว

ขั้นที่ 4 · กับดักที่ 1 — เขียนเลข 1 ต่อท้าย

โจทย์บอกว่ากลุ่มที่มีตัวเดียวให้เขียนแค่ตัวอักษร ถ้าเผลอเขียนเลขต่อท้ายทุกกลุ่ม ผลลัพธ์จะยาวกว่าต้นฉบับและล้นแถวทันที

เขียนเลขทุกกลุ่มแล้วเกิดอะไรขึ้นpython

def compress(chars, always_write_count):
    chars = chars[:]
    w = r = 0
    n = len(chars)
    while r < n:
        ch = chars[r]
        c = 0
        while r < n and chars[r] == ch:
            r += 1
            c += 1
        chars[w] = ch
        w += 1
        if always_write_count or c > 1:
            for d in str(c):
                chars[w] = d      # ถ้าผลลัพธ์ยาวกว่าต้นฉบับ บรรทัดนี้จะล้นแถว
                w += 1
    return w, chars[:w]

for cs in [["a"], ["a", "b", "c"]]:
    print(f"chars={cs}")
    try:
        print("   เขียนเลขทุกกลุ่ม ->", compress(cs, True))
    except IndexError as e:
        print("   เขียนเลขทุกกลุ่ม -> IndexError:", e)
        print("      เพราะ 'a' กลายเป็น 'a1' ซึ่งยาว 2 ช่อง แต่แถวเดิมมีแค่", len(cs), "ช่อง")
    print("   เขียนเลขเมื่อยาวเกิน 1 ->", compress(cs, False), "  <- ถูก")

Output

chars=['a']
   เขียนเลขทุกกลุ่ม -> IndexError: list assignment index out of range
      เพราะ 'a' กลายเป็น 'a1' ซึ่งยาว 2 ช่อง แต่แถวเดิมมีแค่ 1 ช่อง
   เขียนเลขเมื่อยาวเกิน 1 -> (1, ['a'])   <- ถูก
chars=['a', 'b', 'c']
   เขียนเลขทุกกลุ่ม -> IndexError: list assignment index out of range
      เพราะ 'a' กลายเป็น 'a1' ซึ่งยาว 2 ช่อง แต่แถวเดิมมีแค่ 3 ช่อง
   เขียนเลขเมื่อยาวเกิน 1 -> (3, ['a', 'b', 'c'])   <- ถูก

IndexError ที่เห็นไม่ใช่เรื่องบังเอิญ แต่เป็นหลักฐานว่าเงื่อนไข count > 1 คือสิ่งที่ทำให้ทั้งวิธีนี้ปลอดภัย

ขั้นที่ 5 · กับดักที่ 2 — เลขหลายหลัก

ถ้ากลุ่มยาว 12 ตัว เราเขียนเลข 12 ลงช่องเดียวไม่ได้ เพราะหนึ่งช่องเก็บได้ตัวอักษรเดียว

ทางแก้คือแปลงเลขเป็น string ด้วย str(count) แล้ววนใส่ทีละหลัก ซึ่งได้ "1" และ "2" คนละช่อง

กลุ่มยาว 12 ตัว ต้องแตกเลขทีละหลักpython

chars = ["a"] + ["b"]*12
print("chars =", chars, f"(กลุ่ม b ยาว 12)")
w = r = 0; n = len(chars); out = chars[:]
while r < n:
    ch = out[r]; c = 0
    while r < n and out[r] == ch: r += 1; c += 1
    out[w] = ch; w += 1
    if c > 1:
        for d in str(c):
            out[w] = d; w += 1
print("ผลลัพธ์ =", out[:w], "| ความยาว =", w)
print('สังเกตว่า 12 ถูกแยกเป็น "1" กับ "2" คนละช่อง เพราะหนึ่งช่องเก็บได้ตัวเดียว')

Output

chars = ['a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'] (กลุ่ม b ยาว 12)
ผลลัพธ์ = ['a', 'b', '1', '2'] | ความยาว = 4
สังเกตว่า 12 ถูกแยกเป็น "1" กับ "2" คนละช่อง เพราะหนึ่งช่องเก็บได้ตัวเดียว

จุดที่ควรเห็นคือ 13 ช่องถูกย่อเหลือ 4 ช่อง ซึ่งเป็นเหตุผลว่าทำไมท่านี้ปลอดภัยยิ่งขึ้นเมื่อกลุ่มยิ่งยาว

🔓 เฉลยเต็ม พร้อมอธิบายทีละบรรทัด (ลองเองก่อนนะ)พับไว้ด้านใน — คลิกเมื่อพร้อมดู

คำตอบpython

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0                 # ตำแหน่งที่จะเขียนผลลัพธ์ตัวถัดไป
        read = 0                  # ตำแหน่งที่กำลังอ่านของเดิม
        n = len(chars)

        while read < n:
            ch = chars[read]
            count = 0

            # นับกลุ่มนี้ให้จบก่อน พอออกจากลูปนี้ read จะไปหยุดที่หัวกลุ่มถัดไปพอดี
            while read < n and chars[read] == ch:
                read += 1
                count += 1

            chars[write] = ch     # เขียนตัวอักษรของกลุ่ม
            write += 1

            if count > 1:         # เขียนเลขเฉพาะกลุ่มที่ยาวเกิน 1 ไม่งั้นผลลัพธ์จะยาวกว่าเดิม
                for d in str(count):   # เลขหลายหลักต้องแตกทีละหลัก
                    chars[write] = d
                    write += 1

        return write              # ความยาวใหม่ ของที่ค้างท้ายแถวไม่ต้องสนใจ

อ่านโค้ดทีละส่วน

write กับ read แยกกันคนละตัว เพราะทำหน้าที่ต่างกันและเดินคนละจังหวะ
ลูปในนับกลุ่มให้จบก่อนเขียนอะไรลงไป ทำให้ตอนเขียน read เดินผ่านกลุ่มนั้นไปแล้วเรียบร้อย
เงื่อนไข read < n ในลูปในต้องอยู่ซ้ายสุด เพื่อไม่ให้อ่าน chars[read] เกินขอบลิสต์
count > 1 เป็นเงื่อนไขที่รับประกันว่าผลลัพธ์ไม่ยาวกว่าต้นฉบับ จึงไม่ล้นแถว
str(count) แปลงเลขเป็นข้อความเพื่อวนใส่ทีละหลัก รองรับกลุ่มที่ยาวเป็นสิบเป็นร้อย
return write คืนความยาวใหม่ ตามที่โจทย์ขอ

ต้นทุน

เวลา O(n) เพราะ read เดินหน้าเท่านั้นไม่เคยย้อนกลับ จึงแตะแต่ละช่องครั้งเดียว · หน่วยความจำเพิ่ม O(1) เพราะใช้ตัวแปรไม่กี่ตัวและเขียนทับในลิสต์เดิม

เช็คลิสต์ก่อนกดส่ง

ทดสอบ ["a"] ต้องได้ 1 และ chars ยังเป็น ["a"] ไม่ใช่ "a1"
ทดสอบ ["a","b","c"] ที่ไม่มีกลุ่มซ้ำเลย ต้องได้ 3 และไม่มีเลขโผล่มา
ทดสอบกลุ่มที่ยาวเกิน 9 เพื่อเช็คว่าแตกเลขหลายหลักถูก
ตรวจว่ามีเงื่อนไข count > 1 ก่อนเขียนเลข
ตรวจว่า return ความยาว ไม่ใช่ return ลิสต์

ท่านี้จะได้ใช้อีกแน่นอน

ตัวชี้สองตัวเดินตามกันบนแถวเดียวคือท่าเดียวกับที่หมวด Two Pointers เรียกว่า slow กับ fast pointer ชื่อต่างกันแต่กลไกเดียวกันเป๊ะ ถ้าเข้าใจข้อนี้แล้ว หมวดถัดไปจะง่ายขึ้นมาก