ได้ตัวเลข n ต้องการสร้างสตริงตัวพิมพ์เล็กความยาว n+1 ที่ทุกตัวอักษรมีค่า lexicographically greater than ตัวถัดไป (คือ strictly decreasing string)
ตัวอย่าง
Input: 15
Output: ponmlkjihgfedcba
การวิเคราะห์
สตริงที่ strictly decreasing ยาวที่สุดจาก a-z คือ zyxwvutsrqponmlkjihgfedcba (26 ตัวอักษร)
ถ้า n+1 ≤ 26: ตัด suffix ของสตริงด้านบน
ถ้า n+1 > 26: ต้องวนซ้ำ pattern (แต่โจทย์อาจจำกัด n ≤ 25)
Python Implementation
def generate_decreasing_string(n):
"""สร้าง strictly decreasing string ความยาว n+1"""
# Base string: z to a
base = "zyxwvutsrqponmlkjihgfedcba"
length = n + 1
if length <= 26:
# ตัดจากตำแหน่งที่เหมาะสม
start = 26 - length
return base[start:]
else:
# วนซ้ำ pattern (ถ้าอนุญาต)
full_cycles = length // 26
remainder = length % 26
result = base * full_cycles
if remainder > 0:
result += base[26 - remainder:]
return result
# ทดสอบ
for n in [1, 2, 3, 15, 25, 26, 27]:
result = generate_decreasing_string(n)
print(f"n={n}, len={len(result)}: {result}")
ผลลัพธ์
n=1, len=2: ba
n=2, len=3: cba
n=3, len=4: dcba
n=15, len=16: ponmlkjihgfedcba
n=25, len=26: zyxwvutsrqponmlkjihgfedcba
n=26, len=27: zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcba
n=27, len=28: zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcba
วิธีต้นฉบับ (จากโจทย์)
def show_string(n, str_chars):
"""Original algorithm from problem"""
temp_str = ""
extra = n % 26
if extra >= 1:
for i in range(26 - (extra + 1), 26):
temp_str += str_chars[i]
count = n // 26
for i in range(1, count + 1):
for j in range(26):
temp_str += str_chars[j]
return temp_str
# ทดสอบ
n = 15
str_chars = "zyxwvutsrqponmlkjihgfedcba"
print(show_string(n, str_chars)) # ponmlkjihgfedcba
การทำงานของ Original Algorithm
n = 15
extra = 15 % 26 = 15
count = 15 // 26 = 0
# extra >= 1: เพิ่ม chars ตัวสุดท้าย 15 ตัว
# range(26 - 16, 26) = range(10, 26) → indices 10 to 25
# str_chars[10:] = "ponmlkjihgfedcba" ✓
# count = 0: ไม่เข้าลูปเพิ่ม full cycles
Generalized Solution
def decreasing_string(length, alphabet="zyxwvutsrqponmlkjihgfedcba"):
"""สร้าง strictly decreasing string ความยาวที่กำหนด"""
if length <= len(alphabet):
return alphabet[len(alphabet) - length:]
# สำหรับ length > alphabet size
# ต้องมี repeated characters → ไม่ strictly decreasing ได้
raise ValueError(f"Cannot create strictly decreasing string of length {length} "
f"with alphabet size {len(alphabet)}")
# หากอนุญาตให้ wrap around (ไม่ strictly decreasing แล้ว)
def decreasing_string_wrap(length, alphabet="zyxwvutsrqponmlkjihgfedcba"):
result = ""
while len(result) < length:
remaining = length - len(result)
take = min(remaining, len(alphabet))
result += alphabet[len(alphabet) - take:]
return result
สรุป
- Strictly decreasing string สูงสุด 26 ตัวอักษร (a-z)
- ใช้ suffix ของ "zyxwvutsrqponmlkjihgfedcba"
- สำหรับ n=15 → ความยาว 16 → ตัด 16 ตัวท้าย → "ponmlkjihgfedcba"
- Original algorithm จัดการ wrap-around ด้วย modulo
