Python - หาสตริงพิมพ์เล็กเล็กซิกอกราฟิกที่สุด ความยาว k และระยะทาง n

โจทย์: กำหนดตัวเลข n และ k หา สตริงพิมพ์เล็ก (lowercase string) ที่มีความยาว k และ "ระยะทาง" (Distance) เท่ากับ n ที่ เล็กซิกอกราฟิกที่สุด (Lexicographically Smallest)

นิยามระยะทาง: ผลรวมของลำดับตัวอักษรในอัลฟาเบท (a=1, b=2, ..., z=26)

ตัวอย่าง

Input: n = 15, k = 3
Output: "aam"
เหตุผล: "aam" = 1 + 1 + 13 = 15 เป็นสตริงเล็กซิกอกราฟิกที่สุดความยาว 3 ระยะทาง 15

อัลกอริทึม: Greedy จากขวาไปซ้าย

เพื่อให้ได้สตริงเล็กซิกอกราฟิกที่สุด ให้ใส่ค่ามากที่สุดที่ ขวาสุด (Least Significant Position)

ขั้นตอนการทำงาน

เริ่มต้นทุกตัวเป็น 'a' (ค่า 1) → dist = [1] * k
คำนวณ credit = n - k (คงเหลือหลังจากเติม 'a' ทั้งหมด)
จากขวาไปซ้าย (i = k-1 ถึง 0):
- เพิ่มค่าที่ i มากที่สุดเท่าที่จะทำได้ (สูงสุด 25 → 'z')
- val = min(credit, 25)
- dist[i] += val
- credit -= val
แปลง dist เป็นสตริง: chr(d - 1 + ord('a'))

โค้ด Python

def solve(n, k):
    dist = [1] * k          # เริ่มต้นทุกตัวเป็น 'a' (ค่า 1)
    credit = n - k          # คงเหลือต้องกระจาย
    i = k - 1               # เริ่มจากขวาสุด
    
    while credit > 0:
        val = min(credit, 25)  # เพิ่มได้สูงสุด 25 (ถึง 'z')
        dist[i] += val
        credit -= val
        i -= 1
    
    # แปลงตัวเลขเป็นตัวอักษร: 1→a, 2→b, ..., 26→z
    return "".join(chr(d - 1 + ord("a")) for d in dist)

# ทดสอบ
n = 15
k = 3
print(solve(n, k))  # Output: aam

การทำงานทีละขั้นตอน (Trace)

n=15, k=3

Step	dist	credit	i	val	คำอธิบาย
เริ่มต้น	[1, 1, 1]	12	2	-	a a a (sum=3)
1	[1, 1, 1+12=13]	0	1	12	เพิ่ม 12 ที่ index 2 → m
จบ	[1, 1, 13]	0	-	-	a a m → "aam"

ความซับซ้อน

Time Complexity: O(k) - ลูปสูงสุด k รอบ
Space Complexity: O(k) - อาร์เรย์ dist

การทดสอบเพิ่มเติม

print(solve(3, 3))      # "aaa" (1+1+1=3)
print(solve(78, 3))     # "zxz" (26+24+26=76? wait...) 
# 78-3=75 credit, dist=[1,1,1]
# i=2: +25→26, credit=50
# i=1: +25→26, credit=25
# i=0: +25→26, credit=0
# [26,26,26] → "zzz" sum=78 ✓
print(solve(78, 3))     # "zzz"
print(solve(27, 2))     # "az" (1+26=27)
print(solve(52, 2))     # "zz" (26+26=52)

ข้อจำกัด

ต้องมี k ≤ n ≤ 26*k มิฉะนั้นไม่มีคำตอบ
หาก n < k → ไม่สามารถสร้างได้ (ระยะทางน้อยกว่าจำนวนตัวอักษร)
หาก n > 26*k → ไม่สามารถสร้างได้ (ระยะทางมากกว่าสูงสุด)