CareerCup

In Java:

public static String findLongestRepeat(String str) {
		int length = str.length();
		String retVal = "";
		for (int i = 1; i < length; i++) {
			ArrayList<String> substrings = new ArrayList<String>();
			for (int j = 0; j <= length - i; j++) {
				String aString = str.substring(j, j+i-1);
				substrings.add(aString);
			}
			for (int k = 0; k < substrings.size(); k++) {
				if (Collections.frequency(substrings, substrings.get(k)) >= 2) {
					retVal = substrings.get(k);
					continue;
				}
			}
		}
		return retVal;
	}

This is standard application of suffix tree. Lookup longest repeated substring.

public static String findSubstring(String input){
    String substring="";
    for(int i=0; i<input.length(); i++){
      String possibleSubstring="";
      char c=input.charAt(i);
      int j=input.indexOf(c,i+1);
      if( j>0){
        int k=0;
        while(j+k<input.length() && input.charAt(i+k)==input.charAt(j+k) ){
          possibleSubstring+=input.charAt(i+k++);
        }
      }
      if( possibleSubstring.length()>substring.length() ){
        substring=possibleSubstring;
      }
    }
    return substring;
  }

function longestSubstring($S) {
    $L = [];
    $z = 0;
    $ret = [];
    $m = strlen($S) - 1;
    $n = strlen($S);
    for($i=0; $i< $m; ++$i) {
        for($j=$i+1; $j< $n; ++$j) {
            if($S[$i] === $S[$j]) {
                if($i === 0 || $j === 0) {
                    $L[$i][$j] = 1;
                } else {
                    $L[$i][$j] = $L[$i-1][$j-1] + 1;
                }
                if($L[$i][$j] >= $z) {
                    if($L[$i][$j] > $z) {
                        $z = $L[$i][$j];
                        $ret = [];
                    }
                    $ret[] = substr($S,$i-$z+1,$z);
                }
            } else {
                $L[$i][$j] = 0;
            }
        }
    }
    //print_r($L);
    return $ret;
}

var_dump(longestSubstring("hello, mr. yellow")); // "ello"
var_dump(longestSubstring("today is a good time to sing and toddle")); // "tod", "d t", " to"

Finds *all* the longest substrings.

O(n^2). I don't think you can solve it any faster than that.

If you just did it brute force it would take you O(n^3) but you can do better.
Looks like a job for dynamic programming. Its dynamic and its programming and it seems to be what employers want candidates to demonstrate a mastery of, though I don’t think it rarely if ever gets used in my experience. Dynamic programming should take O(n^2) + O(n) space;
Let's consider a matrix m[x][y] let it be the number of matches you get starting when s[x] is aligned with s[y] going backward in the strings. If x == y everything matches back to the start of the string and this does not count. The case where x1 == y1 is the same as y1 == x2 so we need not consider both the cells above the diagonal or below it. Just choose one triangle to consider;
If(s[x] == s[y]) then m[x][y] = m[x-1][y-1] + 1;
Else m[x][y] = 0 ;
If we compute it in the right order, we can reuse matrix rows, only keeping 2 of them.
We there for index like so: m[x][y] -> m[x][y%2]
So we get something like this:

#include <cstdlib>

using namespace std;
#include <string.h>

template<class DATA> // this is a handy little class for 2 d matrixes  
class Two_D_MTX
{
public:
    
    Two_D_MTX(int x,int y)
    {
        data = new DATA[x*y];
        max_x = x;
        max_y = y;
    }
    
    ~Two_D_MTX()
    {
        delete[] data;
    }
    
    DATA *operator[](int x)
    {
        return &data[x * max_y]; 
    }
       
private:
     DATA *data;  
     int max_x; 
     int max_y;
};

int dynamic_repetition(char * s)
{
    int l = strlen(s);
    
    if(l < 2) return 0;
    if(1 == 2) return s[0] == s[1]? 1:2;
    
    Two_D_MTX<int> m(l,2);
    
    int best = 0;
    
    for(int y = 1; y < l; y++)
    {
        m[0][y%2] = (s[0] == s[y])?1:0;
        
        for(int x = 1; x < y; x++)
        {
            if(s[x] != s[y])
            {
                m[x][y%2] = 0;
            }
            else // s[x] == s[y]
            {
                int temp = 1 + m[x-1][(y-1)%2];
                m[x][y%2] = temp;
                best = (temp > best)? temp: best; // max(temp,best);
            }
        }
    }
    
    return best;
}


int main(int argc, char** argv) {

    char s[] = "abcabdsetgddfgsfdgsabcsd";
    int out = dynamic_repetition(s);
    
    return 0;
}

You might be able to do better sorting something called a prefix array though I am not quite sure how to analyze this.
I will try this out with some big examples and get back to you all.

Actually I meant suffix array though prefix array might do as well. While I am still uncertain if the big O time for constructing a properly sorted suffix array would be n log n or n^2 log n it looks like the search to find the longest match would take O(n^2) so why bother.
Still you might want to check out suffix and prefix arrays for future reference.