4
\$\begingroup\$

I recently interviewed with a company for software engineering position. I was asked the question of finding the longest unique sub-string in a string.

My algorithms was as follows:

Start from the left-most character, and keep storing the character in a hash table with the key as the character and the value as the index_where_it_last_occurred. Add the character to the answer string as long as its not present in the hash table. If we encounter a stored character again, I stop and note down the length. I empty the hash table and then start again from the right index of the repeated character. The right index is retrieved from the (index_where_it_last_occurred) flag. If I ever reach the end of the string, I stop and return the longest length.

For example, say the string was abcdecfg.

I start with a, store in hash table. I store b and so on till e. Their indexes are stored as well. When I encounter c again, I stop since it's already hashed and note down the length which is 5. I empty the hash table, and start again from the right index of the repeated character. The repeated character being c, I start again from the position 3 ie., the character d. I keep doing this while I don't reach the end of string.

I know there could be better algorithms than this. But I am interested in knowing what the time complexity of this algorithm will be. I believe it'll be \$O(n^2)\$.

import java.util.*;
public class longest
{
    static int longest_length = -1;
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        calc(str,0);    
        System.out.println(longest_length);
    }

    public static void calc(String str,int index)
    {
        if(index >= str.length()) return;
        int temp_length = 0;
        LinkedHashMap<Character,Integer> map = new LinkedHashMap<Character,Integer>();
        for (int i = index; i<str.length();i++) 
        {
            if(!map.containsKey(str.charAt(i)))
            {
                map.put(str.charAt(i),i);
                ++temp_length;
            }
            else if(map.containsKey(str.charAt(i)))
            {
                if(longest_length < temp_length)
                {
                    longest_length = temp_length;
                }
                int last_index = map.get(str.charAt(i));
//              System.out.println(last_index); 
                calc(str,last_index+1);
                break;
            }
        }
        if(longest_length < temp_length)
            longest_length = temp_length;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Could you please clarify what "longest unique sub-string in a string" means? To me, the string itself is its longest sub-string. What do you mean by "unique"? \$\endgroup\$ – toto2 Oct 13 '14 at 15:49
  • \$\begingroup\$ I meant the longest substring with no repetition. \$\endgroup\$ – aandis Oct 13 '14 at 15:50
  • \$\begingroup\$ No repetition of what? You don't see the same character twice? \$\endgroup\$ – toto2 Oct 14 '14 at 2:02
  • \$\begingroup\$ Yes. The longest substring which has no duplicates. \$\endgroup\$ – aandis Oct 14 '14 at 2:33
3
\$\begingroup\$
static int longest_length = -1;

No. Static is useless here and makes you method much less usable. A non-static variable would be better, but actually, why not return a result???

There's no longest_length in Java. Maybe longestLength.

Better, return the substring, the length can be easily obtained from it.

Separated printing and computation, good.

if(index >= str.length()) return;

Spacing (after if). Also according to conventions, you should always use braces (I personally don't).

LinkedHashMap<Character,Integer> map = new LinkedHashMap<Character,Integer>();

Use Java 7 diamonds or Guava's Maps.newLinkedHashMap() to save yourself repeated generics.

You need no linked map.

calc(str,last_index+1);

I find the recursion confusing here. You really do nothing, but a simple loop, so use a loop (Even a goto would be clearer than recursion here).


The algorithm indeed runs in O(n*n), which can be shown with a string like

abcde.... abcde....

where you always run through half of the string. I was assuming an unlimited alphabet here, more precisely the complexity is O(n*alphabetSize) as no runs can be longer than alphabetSize.


A much better O(n) algorithm would keep track of the starting and ending positions. Wherever you see a duplicate, advance the start. Sounds damn simple.

\$\endgroup\$
  • \$\begingroup\$ why is static useless exactly? How does it matter? \$\endgroup\$ – aandis Oct 13 '14 at 10:22
  • \$\begingroup\$ @zack With static variables (unlike constants), you can't call the method from two threads concurrently. Bad enough? You never know, how it's gonna be used. If you need to keep state (which you don't in this question), create an object and keep it there. It's much more flexible and the cost is negligible. \$\endgroup\$ – maaartinus Oct 13 '14 at 10:58
  • \$\begingroup\$ Yeah. But for this use case, it should be fine right? \$\endgroup\$ – aandis Oct 13 '14 at 11:06
  • 1
    \$\begingroup\$ @zack Yes, but it's a good habit just never do it. The best piece of code is stateless (i.e., a pure function) as it's perfectly reproducible and testable. Stateful objects come next. Statics are last, as a static variable is actually a global variable and global variables are evil. \$\endgroup\$ – maaartinus Oct 13 '14 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.