-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
62 lines (61 loc) · 1.94 KB
/
Program.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using System;
using System.Collections.Generic;
using System.Linq;
namespace SwapForLongestRepeatedCharacterSubstring
{
class Program
{
static void Main(string[] args)
{
string text = "baabaaabbbabaabaab";
Console.WriteLine(MaxRepOpt1(text));
}
static int MaxRepOpt1(string text)
{
var record = new List<int>[26];
for (int i = 0; i < text.Length; i++)
{
if (record[text[i] - 'a'] == null)
record[text[i] - 'a'] = new List<int> { i };
else
record[text[i] - 'a'].Add(i);
}
int res = 0;
for (int i = 0; i < record.Length; i++)
if (record[i] != null)
res = Math.Max(res, GetMaxLen(record[i]));
return res;
}
static int GetMaxLen(List<int> index)
{
var list = new List<int[]>();
int li = 0, hi = li + 1;
while (hi < index.Count)
{
if (index[hi] == index[hi - 1] + 1)
hi++;
else
{
list.Add(new int[3] { index[li], index[hi - 1], hi - li });
li = hi;
hi++;
}
}
list.Add(new int[3] { index[li], index[hi - 1], hi - li });
int res = list[0][2];
for (int i = 1; i < list.Count; i++)
{
if (list[i][0] == list[i - 1][1] + 2)
{
if (list.Count > 2)
res = Math.Max(res, list[i][2] + list[i - 1][2] + 1);
else
res = Math.Max(res, list[i][2] + list[i - 1][2]);
}
else
res = Math.Max(res, Math.Max(list[i][2], list[i - 1][2]) + 1);
}
return res;
}
}
}