In this example, you will learn to find the longest substrings without repeating characters. Iterate through the given string, find the longest maximum substrings.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
import java.util.HashSet; import java.util.Set; public class LongestSubstring { private Set<String> subStrList = new HashSet<String>(); private int finalSubStrSize = 0; public Set<String> getLongestSubstr(String input) { //reset instance variables subStrList.clear(); finalSubStrSize = 0; // have a boolean flag on each character ascii value boolean[] flag = new boolean[256]; int j = 0; char[] inputCharArr = input.toCharArray(); for (int i = 0; i < inputCharArr.length; i++) { char c = inputCharArr[i]; if (flag[c]) { extractSubString(inputCharArr,j,i); for (int k = j; k < i; k++) { if (inputCharArr[k] == c) { j = k + 1; break; } flag[inputCharArr[k]] = false; } } else { flag[c] = true; } } extractSubString(inputCharArr,j,inputCharArr.length); return subStrList; } private String extractSubString(char[] inputArr, int start, int end) { StringBuilder sb = new StringBuilder(); for(int i=start; i<end; i++) { sb.append(inputArr[i]); } String subStr = sb.toString(); if(subStr.length() > finalSubStrSize) { finalSubStrSize = subStr.length(); subStrList.clear(); subStrList.add(subStr); } else if(subStr.length() == finalSubStrSize) { subStrList.add(subStr); } return sb.toString(); } public static void main(String a[]) { LongestSubstring mls = new LongestSubstring(); System.out.println(mls.getLongestSubstr("javasimplified")); System.out.println(mls.getLongestSubstr("java_language_is_awesome")); System.out.println(mls.getLongestSubstr("learn_java_be_a_developer")); System.out.println(mls.getLongestSubstr("abbbabaabc")); } } |
When you run above program, the output will be following:
|
1 2 3 4 |
[vasimpl] [_awesom, uage_is] [learn_j] [abc] |