56 lines
1.8 KiB
C#
56 lines
1.8 KiB
C#
using System.Text;
|
||
|
||
public class Solution
|
||
{
|
||
public string LongestPalindrome(string s)
|
||
{
|
||
if (string.IsNullOrEmpty(s))
|
||
return "";
|
||
var str = PrepareString(s);
|
||
var radii = new int[str.Length];
|
||
var set = new HashSet<int>(); // Индексы радиусов для обработки
|
||
var answer = string.Empty;
|
||
|
||
for (var i = 0; i < str.Length; i++)
|
||
{
|
||
var sym = str[i];
|
||
var toRemove = new List<int>();
|
||
foreach (var radiusIdx in set)
|
||
{
|
||
var new_radius = radii[radiusIdx] + 1;
|
||
// Если с новым радиусом выходим за границы
|
||
if (radiusIdx - new_radius < 0 || radiusIdx + new_radius >= str.Length || str[radiusIdx - new_radius] != sym)
|
||
{
|
||
var len = radii[radiusIdx] * 2 + 1;
|
||
if (len > answer.Length)
|
||
answer = str.Substring(radiusIdx - radii[radiusIdx], len);
|
||
toRemove.Add(radiusIdx);
|
||
}
|
||
else
|
||
radii[radiusIdx] = new_radius;
|
||
}
|
||
foreach (var removeIdx in toRemove)
|
||
set.Remove(removeIdx);
|
||
|
||
set.Add(i);
|
||
}
|
||
|
||
foreach (var radiusIdx in set)
|
||
{
|
||
var len = radii[radiusIdx] * 2 + 1;
|
||
if (len > answer.Length || answer == "#")
|
||
answer = str.Substring(radiusIdx - radii[radiusIdx], len);
|
||
}
|
||
|
||
return answer.Replace("#", "");
|
||
}
|
||
|
||
public string PrepareString(string s)
|
||
{
|
||
var sb = new StringBuilder();
|
||
sb.Append('#');
|
||
foreach (var ch in s)
|
||
sb.Append($"{ch}#");
|
||
return sb.ToString();
|
||
}
|
||
} |