Longest repeating subsequence using only LINQ

Question

5.00/5 (1 vote)

See more:

You can't use any loops, if-else, try-catch, recursion and ect.
You can overlaps. In the sequence 1111 the longest repetition is 111. In the sequence 11211 - the longest repetition is 11.

LongestRepetition(new [] {1, 2, 1, 2, 1, 2, 3, 2, 1, 2}) should return new [] {1, 2, 1, 2}.

What I have tried:

I don't know what to try. I solved it without LINQ.

that's my code:

static string LongestRepetition(string str)
        {
            var list = new List<string>();
            var counter = 0;
            var rep = "";

            for (int i = 0; i < str.Length; i++)
            {
                rep = "";
                for (int k = i; k < str.Length; k++)
                {
                    counter = 0;
                    rep += str[k];
                    var startIndex = 0;
                    var indexOf = int.MinValue;
                    while ((indexOf = str.IndexOf(rep, startIndex)) >= 0)
                    {
                        counter++;
                        startIndex = indexOf + 1;
                        if (counter > 1) break;
                    }

                    if (counter > 1)
                    {
                        list.Add(rep);
                    }
                }
            }

            return list.OrderByDescending(x => x.Length).FirstOrDefault();
        }

Posted 6-Mar-18 3:54am

Member 13711733

Updated 6-Mar-18 20:45pm

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Maciej Los · Accepted Answer · 2018-03-06T09:20:00

Solution 1

Member 13711733[^] wrote:
LongestRepetition(new [] {1, 2, 1, 2, 1, 2, 3, 2, 1, 2}) should return new [] {1, 2, 1, 2}.

Why? It should logically return new [] {1, 2, 1, 2, 1, 2}, because it's a longest repetition.

Check this generic linq solution:

C#

public static T[] GetLongestRepetition<T>(T[] list)
{
	
	return list.TakeWhile(o => list.GroupBy(x=>x)
				.Where(grp=>grp.Count()>1)
				.Any(grp=>grp.Key.Equals(o)))
		.ToArray();
}

Usage:

C#

int[] nums = new int[]{1, 2, 1, 2, 1, 2, 3, 2, 1, 2};
var result = GetLongestRepetition(nums);
Console.WriteLine("{0}", string.Join("", result)); //prints 121212
	
string s = "aabaa";
var result1 = GetLongestRepetition(s.ToArray());
Console.WriteLine("{0}", string.Join("", result1)); //prints aa

string num = "1123811238479";
var result2 = GetLongestRepetition(num.ToArray());
Console.WriteLine("{0}", string.Join("", result2)); //prints 1123811238

Note #1: This solution, unfortunatelly, uses a "hidden loop", see: TakeWhile[^]

Note #2: I haven't enough time to test my solution. So, it may need improvements...

Posted 6-Mar-18 9:20am

Maciej Los

Comments

Graeme_Grant 6-Mar-18 23:01pm

5'd

Maciej Los 7-Mar-18 2:00am

Thank you, Graeme.

Member 13711733 7-Mar-18 2:54am

Thanks! But I can't rework it to do the magic without jumping. Do you think it can be done with input

new [] {1, 2, 1, 2, 1, 2, 3, 2, 1, 2})

to return

new [] {1, 2, 1, 2}

Maciej Los 7-Mar-18 3:00am

As i mentioned in my answer - NO. The longest repetition is: {1, 2, 1, 2, 1, 2}

Member 13711733 7-Mar-18 9:07am

In your case if 1212123212 returns 121212, than 11211 should return 111, not 11.

Maciej Los 7-Mar-18 10:53am

Again - NO.
The longest repetition for [11211] is [11].
The longest repetition for [1212123212] is [121212];
The longest repetition for [111211] or [112111] would be [111].
What does the repetition mean? The number of elements that occur consecutively.
Think of it!

Member 13711733 7-Mar-18 10:56am

That's not my definition of repetition. For me repetition is a subsequence that occurs at least twice int the sequence.
121212 - 1212
11211 - 11
111211 - 11
and so on.

Maciej Los 7-Mar-18 11:00am

You didn't mention this in your question. It'is new requirement and this changes everything.

Maciej Los 7-Mar-18 11:08am

BTW:
For [121212] - the repetition, which occurs at least twice, would be [12] and [21]

Member 13711733 7-Mar-18 13:45pm

Yes. And the longest repetition which occurs at least twice is 1212.

Maciej Los 7-Mar-18 14:01pm

Well, you're looking for longest consecutive pairs ;)