[Solved] Code Coach - Longest Common Substring

Question

I'm unable to solve "Longest Common Substring". I keep failing Test #4.

I've tried my code with multiple test cases made by me and found on the Internet, and I've gotten them all correct.

Has anyone solved it? If so, can you give me some non-trivial test cases? If possible, please give me those that made you realize your code was wrong (in case it ever was).

P.S. I won't post any kind of code as the challenge is rated "Hard".

Answer 1

Michele, Aymane Boukrouh yeah sometime online compiler or competitive platform compiler can't handle the load of program which has used some good sense of concepts, and python is considered as slow in execution in comparison with C and C++ so that's why time limit problem can be come in most of the time.

When I solved the same task with the other C family language c, c++ and java and c# the code is worked relatively faster.

Answer 2

Diego yeah CDAQ is coming for me as well, so might some other test case has failed execution. Give me one minute will check again what can be the problem.

Answer 3

Diego I've solved it with taking trival test case something like this

Test case:-
I've get problem in something like this so it might possibly the case similar with you but not sure.
ABACDAQ BACDAQA ACDAQAW XYZCDAQ

Answer 4

Aymane Boukrouh yes but I'm eager to use python First as it gives an idea how to code in different languages and it is faster and easier in writing but slow sometimes in execution.

Answer 5

I have solved it (in Python) and I didn't seem to have any problem with Test Case #4.

Have you checked if there were multiple strings of the longest length and that you submitted the first one alphabetically?

Edit: Diego, I've just rechecked my code with my own example and my code submitted the last string alphabetically, rather than the first.

Answer 6

Russ GAWEN STEASY
Thanks everyone for answering! Aymane Boukrouh pointed that it could just be that my code is too slow and hits TLE.

I re-checked my code and there were quite a lot of unnecesary calculations performed. I've re-written it and it now works perfectly.

Answer 7

Russ Yes, I use the "less than" (<) operator to check if a common substring with equal length than the current maximum is alphabetically "lower".

Answer 8

Michele it does find abcd, there is no error in the program itself. It is probably a TLE error, because the answers are all correct.

Answer 9

GAWEN STEASY yes, I noticed this problem also, and it is not SL fault. It also happens to me a lot on Google Kick Start, so I guess this is the downside of using python in challenges.

Answer 10

Michele send me your code when you're done please, also C++ code if you can

Answer 11

Keith MacIntyre Why are you sharing my code if it's not related to question?

Answer 12

Found the solution yet ?

Answer 13

Are you checking for more than 1 longest substring?
So if you have two are the same length are you returning the lowest alphabetically?

Here are my test cases. It should find abcd.
word1 = "xzyxyabcdzzabcdpzy";
word2 = "zzxzzabzbabcdbzxzyx"

Answer 14

Michele python, but as he said, it is now working fine

Answer 15

Sure, c/c++ is faster, but certainly there are non-optimal ways to approach this problem. I'll have to try it in python.

Answer 16

GAWEN STEASY What result do you get for your test case? I get "CDAQ", which seems to be correct.

Answer 17

Ok great!

Answer 18

// Hello where. Here is My version on C#. it pass all 6 tests:
https://www.sololearn.com/ru/compiler-playground/c81zxq1Buzf4

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
public static void Main()
{
string[] words = Console.ReadLine().Split(' ');
Array.Sort(words, (x, y) => x.Length.CompareTo(y.Length));
string word = words[0];
int length = word.Length;

for (int i = length; i > 0; i--)
{
HashSet<string> substrings = new HashSet<string>();
for (int j = 0; j <= length - i; j++)
{
substrings.Add(word.Substring(j, i));
}

List<string> ok = substrings.Where(ss => words.Skip(1).All(w => w.Contains(ss))).OrderBy(s => s).ToList();

if (ok.Any())
{
Console.WriteLine(ok[0]);
break;
}
}
}
}

Answer 19

What language did you code it in?

Answer 20

This app seems legit so far