Chương trình tìm chuỗi con đẹp dài nhất bằng Python

Giả sử chúng ta có một chuỗi s. Chúng ta phải tìm chuỗi con đẹp nhất của s. Đối với một chuỗi s, nó sẽ được cho là tốt khi, đối với mỗi chữ cái trong bảng chữ cái trong s, nó xuất hiện ở cả hai chữ hoa và thường. Nếu có nhiều chuỗi con như vậy, thì trả về chuỗi con của lần xuất hiện sớm nhất.

Vì vậy, nếu đầu vào là s =​​"ZbybBbz", thì đầu ra sẽ là "bBb" vì nó chứa chữ B viết thường và viết hoa.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• cur_max:=-1

• res:=chuỗi trống

• đối với tôi trong phạm vi từ 0 đến kích thước của s, thực hiện

  • c:=s [i]

  • upper:=một tập hợp mới

  • thấp hơn:=một tập hợp mới

  • nếu c là chữ thường thì

    • thêm c vào dưới

  • nếu c là chữ hoa thì

    • thêm c vào chữ hoa nhưng trước khi chuyển nó thành chữ thường

  • đối với j trong phạm vi i + 1 đến kích thước của s, thực hiện

    • c:=s [j]

    • nếu c là chữ thường thì

      • thêm c vào dưới

    • nếu c là chữ hoa thì

      • thêm c vào chữ hoa nhưng trước khi chuyển nó thành chữ thường

    • nếu trên giống với dưới thì

      • nếu j-i> cur_max thì

        • cur_max:=j-i

        • res:=chuỗi con của s [từ chỉ mục i đến j + 1]

• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

def solve(s):
   cur_max= -1
   res=""
   for i in range(len(s)):
      c = s[i]
      upper = set()
      lower = set()
      if c.islower():
         lower.add(c)
      if c.isupper():
         upper.add(c.lower())
      for j in range(i+1,len(s)):
         c = s[j]
         if c.islower():
            lower.add(c)
         if c.isupper():
            upper.add(c.lower())
         if upper == lower:
            if j-i>cur_max:
               cur_max = j-i
               res = s[i:j+1]
   return res
s = "ZbybBbz"
print(solve(s))

Đầu vào

"ZbybBbz"

Đầu ra

bBb