I have a problem and I already solved it, but I am searching for enhancement.

pythonatSheriff

Full Stack Web Developer
Joined
Dec 15, 2021
Messages
25
Location
Egypt
Programming Experience
1-3
The problem is :

((Have the function MathChallenge(str) take the str parameter being passed and determine if there is some substring K that can be repeated N > 1 times to produce the input string exactly as it appears. Your program should return the longest substring K, and if there is none it should return the string -1.

For example: if str is "abcababcababcab" then your program should return abcab because that is the longest substring that is repeated 3 times to create the final string. Another example: if str is "abababababab" then your program should return ababab because it is the longest substring. If the input string contains only a single character, your program should return the string -1. ))

My solutions is :
my solution to math problem:
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;


class MainClass
{

  public static void Main(string[] arg1)
  {
        //abcababcababcab
        string str = "abababababab";

        int count = 0;
        for(var i=0; i<str.Length; i++)
        {
            count = count + 1;
        }
        Console.WriteLine(count);

        int division = 0;
        if(count%2 == 0)
        {
            //Console.WriteLine("can divide on 2");
            division = 2;
            
        }
        else if(count%3 == 0)
        {
            //Console.WriteLine("can divide on 3");
            division = 3;
        }


        char[] LooseLetters = str.ToCharArray();
        int LettersCount = (LooseLetters.Length)/(division);
        StringBuilder part1 = new StringBuilder(str);
        if(division == 2)
        {
            part1.Insert(LettersCount, ",");
            Console.WriteLine(part1);
        }
        else if(division == 3)
        {
            part1.Insert(LettersCount, ",");
            part1.Insert((2*LettersCount)+1, ",");
            Console.WriteLine(part1);
        }

        string strConverter = part1.ToString();

        List<string> DuplicateString = strConverter.Split(",").ToList();
        // foreach(var item in DuplicateString)
        // {
        //     Console.WriteLine(item);
        // }

        string result = "";

        if(division == 2)
        {
            if(DuplicateString[0] == DuplicateString[1])
            result = DuplicateString[0];
            else
            result = "-1";
        }
        else if(division == 3)
        {
            if(DuplicateString[0] == DuplicateString[1] && DuplicateString[0] == DuplicateString[2])
            result = DuplicateString[0];
            else
            result = "-1";
        }

        Console.WriteLine(result);

  }

}


Now, I feel like it can be done using (Linq) methods, although I read most of the methods, or there is a simpler solution, so I would like to know to increase my knowledge.
Thanks in advance.
 
Even if your code works that's technically a fail, since you're required to write a function named MathChallenge that take a single string parameter.
function MathChallenge(str) take the str parameter
 
Another way to do it:
C#:
string MathChallenge(string input)
{
    for (int i = 2; i <= input.Length / 2; i++) //possible parts 2 to length/2
    {
        if (input.Length % i == 0) //string divisible by i
        {
            var partlength = input.Length / i;
            var part = input.Substring(0, partlength);
            if (AllPartsEqual(input, part))
                return part;       
        }
    }
    return "-1";
}

bool AllPartsEqual(string input, string part)
{
    for (int i = 1; i < input.Length / part.Length; i++)
    {
        if (input.Substring(i * part.Length, part.Length) != part)
            return false;
    }
    return true;
}
 
Last edited:
Updated the code in post 3, there was a bug or three.
 
Here are three alternatives to if (AllPartsEqual(input, part)) (line 9 in post 3).
After string split by part there should be nothing left:
C#:
if (input.Split(new string[] { part }, StringSplitOptions.RemoveEmptyEntries).Length == 0)
A regex expression "(part){i}" meaning part repeated i times
C#:
if (Regex.IsMatch(input, $"({part}){{{i}}}"))
Linq repeated string
C#:
if (string.Concat(Enumerable.Repeat(part, i)) == input)
 
Then a pure regex version. Logic is (group of one or more chars) repeated 1 or more times (\1 is backreference, + is repeat, greedy). Match must equal input string (same length) and not just a part of it. Return group value.
C#:
string MathChallenge(string input)
{
    var m = Regex.Match(input, "(.+)\\1+");
    if (m.Success && m.Length == input.Length)
        return m.Groups[1].Value;
    return "-1";
}
MatchChallenge would probably be a more suitable function name in my opinion.
 
Interesting, but apparently that interview question has another dimension to it. Solve the same problem in O(n) instead of O(n^2) time complexity.
 
Many thanks for you JohnH for enlightening me with all these aspects that I should revisit to refresh my memory. And thank you SkyDiver for the hint. Apparently, I studied a lot of things THEORITICALLY, and of course I did not need them to built CMS as the steps in DotNetCore MVC don't enforce you to use algorithm, so NO practical training on algorithm had happened. But let me ask you naive question, do I really want to know all of these although the real work (as building website or CMS) is a conventional work? I know that maybe some clients want to add feature, but I feel like I will not invent the wheel, I will go see how this feature built into the system and try to make my way through. Don't get me wrong, I am not saying that algorithm and data structure is not important, I know they are, I am just curious about how I will use them in my daily work. Thanks.
 
Last edited:
When your website or CMS is running slow, you need to be able to analyze why it is running slow. Often a better algorithm or data structure gets your more bang for your buck than better hardware or more hardware.
 
Interesting, but apparently that interview question has another dimension to it. Solve the same problem in O(n) instead of O(n^2) time complexity.
Like this?
C#:
if (AllPartsEqual(input, partlength))
    return input.Substring(0, partlength);
C#:
bool AllPartsEqual(string input, int partlength)
{
    for (int i = 0; i < input.Length / partlength - 1; i++) // loop parts (0 to parts-1)
    {
        for (int j = 0; j < partlength; j++) // loop chars in part
        {
            int index = i * partlength + j;
            if (input[index] != input[index + partlength])
                return false;
        }
    }
    return true;
}
 
Typically, nested loops suggest O(n ^ nestingDepth) behavior unless it can be shown that the nesting only processes part of input just once.
 
So how to compare three or more parts with a single loop? I thought O was also about memory used.
 
Computer science leaning interview questions from Amazon and Google expect their new hires to know Knuth-Morris-Pratt by heart, I suppose. The idea is that KMP will build a table that makes it obvious whether there is a leading substring that also matches a trailing substring and that table cam be built in O(n). The explanation in GeeksForGeeks was a bit over my head with current brain fog from chemo.

For me dynamic programming questions like these throw me off. I prefer the more understandable brute force approaches.
 
A combination of the previous two AllPartsEqual, it scans remaining string only once (but must compare chars of first part each time) and doesn't create new strings. For all practical purposes it does the same as the version in post 11, only with a single loop. It looks much simple though. I have no better idea.
C#:
bool AllPartsEqual(string input, int partlength)
{
    for (int i = partlength; i < input.Length; i++)
    {
        if (input[i] != input[i % partlength])
            return false;
    }
    return true;
}
 
Back
Top Bottom