Introduction

In this blog post, we will explore how to solve the LeetCode problem "2663" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

A string is beautiful if: It consists of the first k letters of the English lowercase alphabet. It does not contain any substring of length 2 or more which is a palindrome. You are given a beautiful string s of length n and a positive integer k. Return the lexicographically smallest string of length n, which is larger than s and is beautiful. If there is no such string, return an empty string. A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b. For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c. Example 1: Input: s = "abcz", k = 26 Output: "abda" Explanation: The string "abda" is beautiful and lexicographically larger than the string "abcz". It can be proven that there is no string that is lexicographically larger than the string "abcz", beautiful, and lexicographically smaller than the string "abda". Example 2: Input: s = "dc", k = 4 Output: "" Explanation: It can be proven that there is no string that is lexicographically larger than the string "dc" and is beautiful. Constraints: 1 <= n == s.length <= 105 4 <= k <= 26 s is a beautiful string.

Explanation

• Iterate from the end: Start from the last character of the string s and move towards the beginning.
  • Increment and Validate: For each character, try incrementing it to the next possible character (up to the k-th letter). Check if the incremented character creates a palindrome of length 2 or 3 with its preceding characters.
  • Construct the result: If a valid increment is found, update the current character and fill the remaining characters with the smallest possible valid character ('a') while maintaining the beautiful string property. If no valid increment is found, move to the previous character. If we reach the beginning and cannot find a valid increment, it means no larger beautiful string exists.

• Runtime Complexity: O(n*k), where n is the length of the string and k is the alphabet size.
• Storage Complexity: O(n), where n is the length of the string.

Code

    def solve():
    s = input()
    k = int(input())
    n = len(s)
    chars = [chr(ord('a') + i) for i in range(k)]

    s_list = list(s)

    for i in range(n - 1, -1, -1):
        for char in chars:
            if char > s_list[i]:
                if i > 0 and s_list[i-1] == char:
                    continue
                if i > 1 and s_list[i-2] == char:
                    continue

                s_list[i] = char
                for j in range(i + 1, n):
                    for c in chars:
                        valid = True
                        if j > 0 and s_list[j-1] == c:
                            valid = False
                        if j > 1 and s_list[j-2] == c:
                            valid = False

                        if valid:
                            s_list[j] = c
                            break
                return "".join(s_list)

    return ""

print(solve())