以下是 LeetCode 2663“字典序最小的美丽字符串”的 Go 实现。

解题思路

与 Java 版本一致：

1. 美丽字符串：只包含前 k 个小写字母，且不含长度大于 1 的回文子串
2. 核心检查：只需避免长度为 2 和 3 的回文
3. 贪心策略：从右向左找到第一个可增加的字符，后面填充最小可行字符

Go 代码

```go
func smallestBeautifulString(s string, k int) string {
    arr := []byte(s)
    n := len(arr)
    
    // 从后往前尝试增加
    for i := n - 1; i >= 0; i-- {
        // 尝试当前位置的所有更大字符
        for c := arr[i] + 1; c < byte('a'+k); c++ {
            // 检查是否与前面的字符形成回文
            if i-1 >= 0 && c == arr[i-1] {
                continue
            }
            if i-2 >= 0 && c == arr[i-2] {
                continue
            }
            
            // 找到可行解
            arr[i] = c
            
            // 填充 i 之后的字符为最小可行字符
            for j := i + 1; j < n; j++ {
                for d := byte('a'); d < byte('a'+k); d++ {
                    if j-1 >= 0 && d == arr[j-1] {
                        continue
                    }
                    if j-2 >= 0 && d == arr[j-2] {
                        continue
                    }
                    arr[j] = d
                    break
                }
            }
            return string(arr)
        }
    }
    
    return ""
}
```

更简洁的版本（使用辅助函数）

```go
func smallestBeautifulString(s string, k int) string {
    arr := []byte(s)
    n := len(arr)
    
    // 检查字符 c 放在位置 pos 是否合法
    isValid := func(pos int, c byte) bool {
        if pos-1 >= 0 && c == arr[pos-1] {
            return false
        }
        if pos-2 >= 0 && c == arr[pos-2] {
            return false
        }
        return true
    }
    
    // 从后往前尝试
    for i := n - 1; i >= 0; i-- {
        // 尝试更大的字符
        for c := arr[i] + 1; c < byte('a'+k); c++ {
            if !isValid(i, c) {
                continue
            }
            
            arr[i] = c
            
            // 填充后面的位置
            for j := i + 1; j < n; j++ {
                for d := byte('a'); d < byte('a'+k); d++ {
                    // 临时赋值以检查合法性
                    old := arr[j]
                    arr[j] = d
                    if isValid(j, d) {
                        break
                    }
                    arr[j] = old
                }
            }
            return string(arr)
        }
    }
    
    return ""
}
```

优化版本（预计算填充）

```go
func smallestBeautifulString(s string, k int) string {
    arr := []byte(s)
    n := len(arr)
    
    // 从后往前查找可增加的位置
    for i := n - 1; i >= 0; i-- {
        // 尝试增加当前位置
        for c := arr[i] + 1; c < byte('a'+k); c++ {
            // 检查回文条件
            if (i > 0 && c == arr[i-1]) || (i > 1 && c == arr[i-2]) {
                continue
            }
            
            // 找到合法字符
            arr[i] = c
            
            // 填充后续位置为最小字典序
            for j := i + 1; j < n; j++ {
                for d := byte('a'); d < byte('a'+k); d++ {
                    if (j > 0 && d == arr[j-1]) || (j > 1 && d == arr[j-2]) {
                        continue
                    }
                    arr[j] = d
                    break
                }
            }
            return string(arr)
        }
    }
    
    return ""
}
```

示例测试

```go
func main() {
    fmt.Println(smallestBeautifulString("abcz", 26)) // "abdab"
    fmt.Println(smallestBeautifulString("dc", 4))    // ""
    fmt.Println(smallestBeautifulString("ab", 3))    // "ac"
}
```

算法复杂度

· 时间复杂度：O(n * k)，其中 n 为字符串长度，k 为字符集大小
  · 最坏情况需要尝试所有位置和所有字符
· 空间复杂度：O(n)，存储字节数组

关键点说明

1. 回文检查简化：
   · 只需检查与前 1 位（避免 aa 形式）
   · 只需检查与前 2 位（避免 aba 形式）
   · 因为任何长度 ≥4 的回文必然包含长度为 2 或 3 的回文
2. 贪心正确性：
   · 从后往前修改保证了字典序最小
   · 后面的位置填充最小可行字符进一步保证最小性
3. 边界处理：
   · 当 i = 0 时，只需检查与前 2 位（不存在）
   · 当 i = 1 时，只需检查与前 1 位