Longest repeating sequence using linq only

Question

As the title says i have a task to find the longest repeating sequence in a string and it has to be done with linq only - no ifs, no loop, no try, assignment is only allowed on initialization of variables, recursion is allowed. I've found the solution online and i understand what is happening but i can't transform it to linq -I'm not that familiar with it. I would greatly appreciate if someone could help me. Here is a link to what ive found -https://www.javatpoint.com/program-to-find-longest-repeating-sequence-in-a-string.

List<int> a = new List<int> {1, 2, 1, 2, 1, 2, 3, 2, 1, 2};
List<List<int>> aa = new List<List<int>>();
outerLoop(a);

var max = aa.Max(x => x.Count);
var m = from v in aa 
    where v.Count == max
    select v;
    m.Dump();

void outerLoop(List<int> list)
{
List<int> f = new List<int>();
f.AddRange(list.Skip(list.Count-1).Take(list.Count).ToList());
innerLoop(list, list.Skip(1).Take(list.Count).ToList());

f.ForEach(k => outerLoop(list.Skip(1).Take(list.Count).ToList()));
}


void innerLoop(List<int> l, List<int> subList)
{
List<int> f = new List<int>();
f.AddRange(subList.Skip(subList.Count-1).Take(subList.Count).ToList());
var tt = l.TakeWhile((ch, i) => i < subList.Count && subList[i] == ch).ToList();

aa.Add(tt);
f.ForEach(k => innerLoop(l, subList.Skip(1).Take(subList.Count).ToList()));
}

so i came up with this "beauty", i don't think it's good code but i think it works. If anyone is interested and wants to make suggestions how to make it better, they are more than welcome to :)

if input is int[] x= {1, 2, 1, 2, 1, 2, 3, 2, 1, 2} result should be 1212

Answer 1

Give this a go:

List<int> words = new List<int> { 1, 2, 1, 2, 1, 2, 3, 2, 1, 2 };

string result =
    words
        .Select((c, i) => i)
        .SelectMany(i => Enumerable.Range(1, words.Count - i).Select(j => words.Skip(i).Take(j)), (i, w) => new { i, w })
        .GroupBy(x => String.Join(",", x.w), x => x.i)
        .Where(x => x.Skip(1).Any())
        .Select(x => x.Key)
        .OrderByDescending(x => x.Length)
        .First();

That gives me 1,2,1,2.

If you want one that actually works with strings, try this:

var word = "supercalifragilisticexpialidocious";

string result =
    word
        .Select((c, i) => i)
        .SelectMany(i => Enumerable.Range(1, word.Length - i).Select(j => word.Skip(i).Take(j)), (i, w) => new { i, w })
        .GroupBy(x => new string(x.w.ToArray()), x => x.i)
        .Where(x => x.Skip(1).Any())
        .Select(x => x.Key)
        .OrderByDescending(x => x.Length)
        .First();

That gives me ali.

---

Here's a slightly more understandable version:

var word = "supercalifragilisticexpialidocious";

string result =
(
    from i in Enumerable.Range(0, word.Length)
    from j in Enumerable.Range(1, word.Length - i)
    group i by word.Substring(i, j) into gis
    where gis.Skip(1).Any()
    orderby gis.Key.Length descending
    select gis.Key
).First();

Answer 2

Here is my version. It isn't a single LINQ expression, but does use only LINQ. It does return all same length subsequences if there are multiple answers. It should work any type of sequence. It was written to only use standard LINQ methods.

It uses GroupBy with a string key to implement a sequence Distinct. (Because of this trick, lists that contain items with commas might not work right.) In production code, I would use a Distinct with an IEqualityComparer for sequences based on SequenceEqual. It also has a separate step for finding the maximum repeated sequence length and then finding all the matching sequences, in production code I would use a MaxBy extension.

Update: Since I was using GroupBy for DistinctBy, I realized I could just use that to count the subsequence repeats directly rather than search for them.

var repeaters = Enumerable.Range(0, words.Count) // starting positions
                       .SelectMany(n => Enumerable.Range(1, (words.Count - n) / 2).Select(l => words.Skip(n).Take(l).ToList())) // subseqs from each starting position
                       .GroupBy(s => String.Join(",", s), (k, sg) => new { seq = sg.First(), Repeats = sg.Count() }) // count each sequence
                       .Where(sr => sr.Repeats > 1) // only keep repeated sequences
                       .Select(sr => sr.seq); // no longer need counts
var maxRepeaterLen = repeaters.Select(ss => ss.Count()).Max(); // find longest repeated sequence's length
var maxLenRepeaters = repeaters.Where(ss => ss.Count() == maxRepeaterLen); // return all sequences matching longest length