สมมติว่าเรามีสตริง s เราต้องหาสตริงที่เล็กที่สุดเกี่ยวกับศัพท์เฉพาะที่สามารถสร้างได้หากเราสามารถสลับระหว่างอักขระสองตัวในสตริงที่กำหนดได้มากที่สุดหนึ่งครั้ง
ดังนั้น หากอินพุตเป็นเหมือน "zyzx" เอาต์พุตจะเป็น "xyzz"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- temp :=อาร์เรย์ขนาด s และเติม 0
- m:=ขนาด s - 1
- สำหรับฉันในช่วงขนาด s -1 ถึง -1 ลดลง 1 ทำ
- ถ้า s[i]
- ม :=ผม
- ถ้า s[i]
- อุณหภูมิ[i] :=ม.
- สำหรับฉันในช่วง 0 ถึงขนาดของ s ทำ
- a :=temp[i]
- ถ้า s[a] ไม่เหมือนกับ s[i] แล้ว
- ส่งคืนสตริงย่อยของ s [จากดัชนี 0 ถึง i] เชื่อม s[a] สตริงย่อยของ s [จากดัชนี i+1 ถึง a] ต่อ s[i] ต่อสตริงย่อยของ s [จากดัชนี a+1 ถึงปลาย]
ตัวอย่าง
class Solution:
def solve(self, s):
temp = [0]*len(s)
m=len(s)-1
for i in range(len(s)-1, -1, -1):
if s[i]<s[m]: m=i
temp[i] = m
for i in range(len(s)):
a = temp[i]
if s[a] != s[i]:
return s[:i]+s[a]+s[i+1:a]+s[i]+s[a+1:]
return s
ob = Solution()
print(ob.solve("zyzx")) อินพุต
zyzx
ผลลัพธ์
xyzz
