how to extract longest sub string (having distinct consecutive character) from a string in java

Question

I want to extract longest distinct consecutive substring from a string

for eg:

1 )abcdeddd should give

abcde

2) aaabcdrrr

abcd

i wrote this code

        for (int i = 0; i < lines; i++) {

            String s = bf.readLine();
            ArrayList<String> al = new ArrayList<String>();
            TreeMap<Integer, Integer> count = new TreeMap<Integer, Integer>();
            int point = 0;
            for (int j = 0; j < s.length() - 1; j++) {
                if (s.charAt(j + 1) != s.charAt(j)) {
                    Character xyz = s.charAt(j);
                    String news = al.get(point).concat(xyz.toString());
                    al.add(point, news);

                } else if (s.charAt(j + 1) == s.charAt(j)) {
                    point++;

                }

                for (int k = 0; k < al.size(); k++) {

                    count.put(al.get(k).length(), k);

                }

                System.out.println(al.get(count.get(count.size() - 1)));

            }

        }
    } catch (Exception e) {

    }
}

Answer 1

Here is my solution:

    String input = "abcdabcdeabcedeabcdefffff";

    String longest = "";
    String temp = "";

    for(int pos=0; pos<input.length(); pos++) {
        if(temp.isEmpty()) {
            temp = String.valueOf(input.charAt(pos));
        } else if(input.charAt(pos) == temp.charAt(temp.length() - 1) + 1) {
            temp += input.charAt(pos);
        } else {
            temp = String.valueOf(input.charAt(pos));
        }

        if(temp.length() > longest.length())
            longest = temp;
    }

    System.out.println(longest);

You could also use a StringBuilder for temp as it is more efficient for building Strings in Java.

Answer 2

You can try this way too.

    String s = "abcdefgdrrstqrstuvwxyzprr";
    Map<Integer,String> results=new HashMap<>();
    Set<String> set=new LinkedHashSet<>();
    for(int i=0;i<s.length()-1;i++){
        if(s.charAt(i)-s.charAt(i+1)==-1){
            set.add(""+s.charAt(i));
            set.add(""+s.charAt(i+1));
        }else {
            results.put(set.size(), set.toString());
            set=new LinkedHashSet<>();
        }
    }
    System.out.println(results);

Out put:

  {0=[], 3=[r, s, t], 7=[a, b, c, d, e, f, g], 10=[q, r, s, t, u, v, w, x, y, z]}

Now you can see all consecutive chars. and answer is largest one. In this way you can find more than one consecutive substring if they are in same length.

You can get it

 String largest=new ArrayList<>(results.values())
                               .get(results.size()-1).replaceAll("\\[|]|, ","");
 if("".equals(largest)){
   System.out.println("There is not consecutive substring for \""+s+"\"");
 }else {
   System.out.println("largest consecutive substring of \""+s+"\" is "+ largest);
 }

Now out put:

largest consecutive substring of "abcdefgdrrstqrstuvwxyzprr" is qrstuvwxyz

Answer 3

You can iterate/check each of the character starting from character x where x is the starting point of the character checking, then increment to check if the next index of character is corresponds to the next alphabet from the last character.

sample:

String s = "abcdefgdrrstqrstuvwxyzprr";
    int start = s.charAt(0);
    StringBuilder temp = new StringBuilder();
    String temp2 = "";
    boolean done = false;

    for(int i = 0; i < s.toCharArray().length; i++)
    {
        if(s.toCharArray()[i] == start) {
            temp.append(s.toCharArray()[i]);
            start++;
            done = true;
            if(i == s.toCharArray().length-1)
                temp2 = !(temp2.length() > temp.length()) ? temp.toString() : temp2;
        }else
        {
            if(done)
            {
                if(!(temp2.length() > temp.length()))
                    temp2 = temp.toString();
                --i;
            }
            temp = new StringBuilder("");
            done = false;
            start = (i == s.toCharArray().length-1) ? 0 : s.toCharArray()[i+1];
        }
    }

    System.out.println("LONGEST IS: " + temp2);

result:

qrstuvwxyz

And if the test String is abcdeddd the result would be abcde