Longest Substring without duplicate character

 

There can be N number of questions can be framed by using String, like longest substring without duplicate character, substring with repeated characters, most consecutive characters in substring etc., Now let's see simple java code to find the longest substring without duplicate characters with O(N) time complexity.
Longest Substring without duplicate character


public class LongestSubString {

 public static void main(String[] args) {

  String mainStr = "JavaDiscover";

  String longSubStr = longSubString(mainStr);

  System.out.println("ORIGINAL STRING    ::: " + mainStr);
  System.out.println("LONGEST SUB STRING ::: " + longSubStr);
 }

 public static String longSubString(String mainStr) {

  String longStr = "";
  String tmp = "";

  char[] charArray = mainStr.toCharArray();

  for (int i = 0; i < mainStr.length(); i++) {

   if (tmp.contains(charArray[i] + "")) {

    if (longStr.length() < tmp.length()) {
     longStr = tmp;
    }

    tmp = tmp.substring((tmp.indexOf(charArray[i]) + 1), tmp.length());
    tmp = tmp + charArray[i];

   } else {
    tmp = tmp + charArray[i];
   }
  }

  if (longStr.length() < tmp.length()) {
   longStr = tmp;
  }

  return longStr;
 }
}


OUTPUT:



ORIGINAL STRING    ::: JavaDiscover
LONGEST SUB STRING ::: aDiscover

No comments:
Write comments