Algo Ramblings: Longest substring with 2 unique characters



Find the longest substring with at most two unique characters(ASCII) in a given string .
We create a set of length 256 to keep the last index from the left. Whenever we reach a new character and count is still less than or equal to 2 we check if the current substring length is greater than the previous result. If it is we update the result as the current longest substring.
public static String longestTwoUnique(String s) {
char str[] = s.toCharArray();
int[] set = new int[256];
Arrays.fill(set, -1);
int i = 0, j = 0;
String res = "";
int count = 0;
while (j < s.length()) {
if (set[str[j]] == -1) {
set[str[j]] = j;
count++;
if (res.length() <= j - i)
res = s.substring(i, j);
if (count > 2) {
count--;
int nextI = set[str[i]];
set[str[i]] = -1;
i = nextI + 1;
}
} else {
set[str[j]] = j;
if (res.length() <= j - i)
res = s.substring(i, j);
}
j++;
}
if (count <= 2 && res.length() <= j - i)
res = s.substring(i, j);
return res;
}
Read full article from Algo Ramblings: Longest substring with 2 unique characters.

No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts