Python에서 한 번의 스왑으로 사전적으로 가장 작은 문자열을 찾는 프로그램

문자열 s가 있다고 가정하고 주어진 문자열 s의 두 문자 간에 최대 한 번만 교환할 수 있는 경우 만들 수 있는 사전순으로 가장 작은 문자열을 찾아야 합니다.

따라서 입력이 "zyzx"와 같으면 출력은 "xyzz"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• temp :=크기가 s이고 0으로 채워진 배열
• m:=s의 크기 - 1
• s -1 ~ -1 범위 크기의 i에 대해 1 감소, do
  • s[i]
  • m :=나는
• temp[i] :=m
• 0에서 s 크기의 범위에 있는 i에 대해 다음을 수행합니다.
  • a :=온도[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