首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >给定字符串最长子字符串的长度,使其字符重新排列形成回文

给定字符串最长子字符串的长度,使其字符重新排列形成回文
EN

Stack Overflow用户
提问于 2022-12-04 10:27:20
回答 1查看 33关注 0票数 -1
  • 只有小写字符串作为输入。
  • 只有文字作为输入
  • 如果像"@“、”#“这样的字符无效..。都在
  • 查找给定字符串最长子字符串的长度,以便重新排列其中的字符以形成回文。
  • 输出长度

我无法用python进行编程。

请帮帮忙。

我的思路是将初始计数器保持为1(即使一个字母完全不同的单词在默认情况下也有1)。

然后在字母中为每1次匹配添加2次

示例输入:“信函”

示例输出:5#(1(默认为+2( 2"t"s) +2( 2"e"s))

EN

回答 1

Stack Overflow用户

发布于 2022-12-04 12:22:36

您可以使用此代码计算最长子字符串的长度,该子字符串可以重新排列以形成回文:

代码语言:javascript
复制
def longestSubstring(s: str):
 
    # To keep track of the last
    # index of each xor
    n = len(s)
    index = dict()
 
    # Initialize answer with 0
    answer = 0
 
    mask = 0
    index[mask] = -1
 
    # Now iterate through each character
    # of the string
    for i in range(n):
 
        # Convert the character from
        # [a, z] to [0, 25]
        temp = ord(s[i]) - 97
 
        # Turn the temp-th bit on if
        # character occurs odd number
        # of times and turn off the temp-th
        # bit off if the character occurs
        # even number of times
        mask ^= (1 << temp)
 
        # If a mask is present in the index
        # Therefore a palindrome is
        # found from index[mask] to i
        if mask in index.keys():
            answer = max(answer,
                         i - index[mask])
 
        # If x is not found then add its
        # position in the index dict.
        else:
            index[mask] = i
 
        # Check for the palindrome of
        # odd length
        for j in range(26):
 
            # We cancel the occurrence
            # of a character if it occurs
            # odd number times
            mask2 = mask ^ (1 << j)
            if mask2 in index.keys():
 
                answer = max(answer,
                             i - index[mask2])
 
    return answer

该算法基本上是O(N*26)。XOR基本上检查某个字符的数量是偶数还是奇数。对于字符串中的每个字符,每个字符都有一个特定的异或序列,它告诉您哪些字符出现了奇数时间,哪些字符出现了偶数次。如果在过去已经遇到过相同的序列,那么您知道您已经找到了一个回文,因为您已经回到了在XOR序列中开始的位置--也就是在这个点和起点之间出现的每个字符的偶数。如果字符串中的两个点之间出现的每个字符都是偶数,那么您可以在它们之间形成一个回文。奇数长度检查只是检查回文的特例,回文的长度为奇数。如果一个字符出现奇数次,它就会依次假装,它只是假设出现偶数次,以处理字符在奇数长度回文中间的特殊情况。

编辑:这里是指向原始代码和解释的链接。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/74674638

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档