Longest Nonrepeating Substring in A String

I posted this solution to this problem before, but just realised it's been forgotten! So redo and repost it to refresh this O(n) time and space solution.

Idea: moving tail towards to end, adjust head smartly with help of char array or character set. Never go back in one pass!

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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

public class Solution { String longestNonRepeatSubString_char(String input) { if (input == null || "".equals(input) || input.length() == 1) return input; // usually thinking about using set for uniqueness checking // if the target is limited to small set of characters such as ASCII, // then use char array boolean[] existing = new boolean[256];// 256 is extended ascii. index is // the character int head = 0, maxLen = 0; String maxSubstring = null; for (int tail = 0; tail < input.length(); tail++) { // if the current character is existing, then move head to the next // of character being repeated while (existing[input.charAt(tail)]) { // head keeps moving until it moves to the character being // repeated and set it to false // then the loop will exit, and head points to the next valid // start point existing[input.charAt(head)] = false;// every character before // new head position is // marked as not // existing head++; } // normally, when a character is met, it's marked as existing existing[input.charAt(tail)] = true; // evaluate the max for every tail moving forward if (tail - head > maxLen) { maxLen = tail - head; maxSubstring = input.substring(head, tail + 1); } } return maxSubstring; } /** * char array version of implementation * * @param input * @return */ String longestNonRepeatSubString_char(char[] input) { if (input == null || "".equals(input) || input.length == 1) return new String(input); // usually thinking about using set for uniqueness checking // if the target is limited to small set of characters such as ASCII, // then use char array boolean[] existing = new boolean[256];// 256 is extended ascii. index is // the character int head = 0, maxLen = 0; String maxSubstring = null; for (int tail = 0; tail < input.length; tail++) { // if the current character is existing, then move head to the next // of character being repeated while (existing[input[tail]]) { // head keeps moving until it moves to the character being // repeated and set it to false // then the loop will exit, and head points to the next valid // start point existing[input[head]] = false;// every character before new head // position is marked as not // existing head++; } // normally, when a character is met, it's marked as existing existing[input[tail]] = true; // evaluate the max for every tail moving forward if (tail - head > maxLen) { maxLen = tail - head; maxSubstring = new String(input, head, tail - head + 1); } } return maxSubstring; } public static void main(String[] args) { Solution s = new Solution(); System.out .println(s .longestNonRepeatSubString_char("every character before new head position is mark")); System.out .println(s .longestNonRepeatSubString_char("every character before new head position is mark" .toCharArray())); } }