题解 | #密码截取#

解题思路

这道题目实际上是在寻找字符串中的最长回文子串。可以使用中心扩展法来解决：

1. 遍历字符串的每个位置，将其作为回文串的中心
2. 分别处理奇数长度（一个字符为中心）和偶数长度（两个字符为中心）的情况
3. 从中心向两边扩展，直到不满足回文条件
4. 记录并更新最长回文串的长度

代码

#include <iostream>
#include <string>
using namespace std;

// 从中心向两边扩展寻找回文串
int expandAroundCenter(string s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

int main() {
    string s;
    cin >> s;
    
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        // 奇数长度的回文串
        int len1 = expandAroundCenter(s, i, i);
        // 偶数长度的回文串
        int len2 = expandAroundCenter(s, i, i + 1);
        
        maxLen = max(maxLen, max(len1, len2));
    }
    
    cout << maxLen << endl;
    return 0;
}

def expand_around_center(s: str, left: int, right: int) -> int:
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

def longest_palindrome():
    s = input()
    max_len = 0
    
    for i in range(len(s)):
        # 奇数长度的回文串
        len1 = expand_around_center(s, i, i)
        # 偶数长度的回文串
        len2 = expand_around_center(s, i, i + 1)
        max_len = max(max_len, max(len1, len2))
    
    print(max_len)

if __name__ == "__main__":
    longest_palindrome()

import java.util.*;

public class Main {
    public static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);     // 奇数长度
            int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度
            maxLen = Math.max(maxLen, Math.max(len1, len2));
        }
        
        System.out.println(maxLen);
    }
}

算法及复杂度

• 算法：中心扩展法
• 时间复杂度：，其中 为字符串长度
• 空间复杂度：，只需要常数空间