c# - 如何找到最长的子数组，其元素(数字)可以重新排列以在 C# 中形成回文？

Question

这是我的代码

using System;

public class Program
{

     private static string GetLongestPalindrome(string input)
    {
        int rightIndex = 0, leftIndex = 0;
        var x = "";
        string currentPalindrome = string.Empty;
        string longestPalindrome = string.Empty;
        for(int currentIndex = 1; currentIndex < input.Length - 1; currentIndex++)
        {
            leftIndex = currentIndex - 1;
            rightIndex = currentIndex + 1;
            while(leftIndex >= 0 && rightIndex < input.Length)
            {
                if(input[leftIndex] != input[rightIndex])
                {
                    break;
                }
                currentPalindrome = input.Substring(leftIndex, rightIndex - leftIndex + 1);
                if(currentPalindrome.Length > x.Length)
                    x = currentPalindrome;
                leftIndex--;
                rightIndex++;
            }
        }
        return x;
    }

    public static void Main()
    {
        Console.WriteLine(GetLongestPalindrome("12345354987"));
    }
}

输出:

input  = 12345354987,output = 345543.

这里最长的子数组是345354，可以重新排列形成345543，这是一个回文。在上面的代码中，我得到了回文数 45354。但是在使用 C# 重新排列 345543 之后，上面的输入包含最大的回文数是 345354。

Answer 1

婴儿学步...

你的方法做的太多了，把它分解成你可以处理的更小的问题。我们需要解决什么？

1. 从给定的字符串中提取所有可能的子字符串。
2. 验证给定的字符串是否可以突变为单个字符移动位置的回文。

好的，让我们开始吧:

获取所有子串相对容易:

private static IEnumerable<string> GetAllSubSequences(
    this string s)
    => from start in Enumerable.Range(0, s.Length)
       from length in Enumerable.Range(1, s.Length - start)
       select s.Substring(start, length);

或者如果你更喜欢流利的语法:

private static IEnumerable<string> GetAllSubSequences(string s)
    => Enumerable.Range(0, s.Length)
                 .SelectMany(start => Enumerable.Range(1, s.Length - start),
                             (start, length) => s.Substring(start, length));

现在我们需要一种方法来告诉我们给定的字符串是否可以转换为回文。嗯...我们怎样才能轻松做到这一点？我们可以检查所有可能的类次，但这看起来非常困惑和浪费。

回文有两种形式；偶数回文 123321 和非奇数长度 123444321。您是否看到我们可以利用的这两个模式？在前一种情况下，每个字符的总数似乎必须是偶数。后者条件几乎相同，但也必然存在一个且只有一个字符总数不均匀。

好的，让我们实现这个:

private static bool IsRearrangableIntoPalindrome(
    this IEnumerable<char> characters) 
    =>  characters.Count() % 2 == 0 ?
        //all even
        characters.GroupBy(c => c)
                  .All(g => g.Count() % 2 == 0):
        //one odd
        characters.GroupBy(c => c)
                  .Count(g => g.Count() % 2 != 0) == 1; 

现在，我们只需将所有内容放在一起:

var str = "12345354987";
var largestPotentialPalindrome =
    str.GetAllSubSequences()
       .Where(s => s.IsRearrangableIntoPalindrome())
       .OrderBy(s => s.Length)
       .LastOrDefault();

果然，答案是 3453549，这是可以转换为回文的最大子串:3459543(以及其他)。