0

The text of the problem says so: Find the longest substring in a given string formed with words that have 2 or more letters in common(the words must be neighbours in the substring(one after the other)) . Restraint: running time must be lower than O(n^2);

Another restriction is that the programme must have a method that compares 2 words and says if they have 2 or more letters in common. This function must run in O(n) time.

The only way I thought of achieving O(n) time in the method is using Hashtables(as you will see the name of the method which tries to achieve this is "find"). This is my implementation of the problem: 

public class Subiectul1 {
    String str1;

    Subiectul1(String str1){
        this.str1 = str1;
    }

    public boolean find(String str1, String str2){
        Hashtable<String,Integer> hash = new Hashtable<String,Integer>();
        int count = 0;

        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();

        for(int i = 0; i < str1.length(); i++){
            hash.put(String.valueOf(str1.charAt(i)), 1);
        }

        for(int i = 0; i < str2.length(); i++){
            if(hash.containsKey(String.valueOf(str2.charAt(i)))) {
                count++; 
                hash.remove(String.valueOf(str2.charAt(i)));
            }
        }

        if(count >= 2) return true;

        return false;
    }

    public void solve(){
        String[] a_str1 = str1.split(" ");
        int n = a_str1.length;
        int[] lmax = new int[n];
        int[] succ = new int[n];
        int max = 0;
        int pmax = -1;

        lmax[n - 1] = 1;
        succ[n - 1] = -1;

        for(int i = n - 2; i >= 0; i--){
            max = 0;
            pmax = -1;
            for(int j = i + 1; j < n; j++)
                if(find(a_str1[i],a_str1[j]) && (max < lmax[j])){
                    max = lmax[j];
                    pmax = j;
                }

            lmax[i] = max + 1;
            succ[i] = pmax;
        }

        pmax = 0;
        max = lmax[0];

        for(int i = 1; i < n; i++)
            if(lmax[i] > max ) {
                pmax = i;
                max = lmax[pmax];
            }

        int i = pmax;
        while(i != -1){
            System.out.print(a_str1[i] + " ");
            i = succ[i];
        }

    }
}

I would like to know if anyone else has any better ideas as this is the best I could think of.

Lucian Tarna
  • 1,806
  • 4
  • 25
  • 48
  • Can you clarify what you mean by "formed with words that have 2 or more letter in common" ? Maybe provide some example? – Diego Martinoia Jul 16 '15 at 09:57
  • i put "aaaa bbbbbbbb" in this algorithm and the result is "aaaa". put a valid example pls – Matteo Rubini Jul 16 '15 at 10:00
  • Yes. Every word must have 2 or more letters in common with it's neighbour . For example let's take the first word "example" and the second word "ample" then these 2 words have in common more than 2 letters and are eligible. For a bigger string: "Ana o intreaba pe vanzatoare daca are strudel cu mere " should result in "Ana intreaba vanzatoare are strudel mere" . – Lucian Tarna Jul 16 '15 at 10:00
  • The second question on one day. Where does this problem come? http://stackoverflow.com/questions/31445651/words-with-at-least-2-common-letters – Petr Jul 16 '15 at 10:02
  • Haha kitz.. I didn't see he is a classmate of mine more than sure. We are preparing for an admission exam to IT master:P . It is one of the problems given in past years. – Lucian Tarna Jul 16 '15 at 10:03
  • yeah so the other idea is to put a numbered vector . I thought about that then decided a hash is better. What do you guys think ? – Lucian Tarna Jul 16 '15 at 10:04

0 Answers0