Lexi's Leetcode solutions

[phone] 找string中最长的只有两个unique char的substring

Posted on: August 29, 2013

Given a string, find longest substring which contains just two unique characters. 比如ABACDDCB, 返回CDDC。

自己做的O(n)的解法,不用额外空间,但是需要additional data structure。测了几个没问题。

思路:假设d[i – 1]是以arr[i – 1]为结尾的data,已经做好了。那d[i] =

  • 如果arr[i]属于d[i – 1]的那个substring中的两个元素中的某一个,那么d[i]的长度直接是上一个加一。
  • 不属于的话,要把arr[i]和上一个的“最后一段由一个字母组成的sequance“连起来。比如d[i – 1]的结果是BABB,然后arr[i]是C,就想把BB和C连起来生成新的substring BBC然后放在d[i]里。
  • 这样的话,需要记录四个数据:length, index of last sequence ‘s beginning m, the char that is not the last (in above case, is A), and last letter (B)(这个不是必要的,可以用m来读,但是看着方便。
public class Data {
  int len;
  Character last;
  Character notLast;
  int m;// beginning index of last sequense
}
String findLongestSubString(String s) {
  if (s.length() == 0)
    return null;
  Data prev = new Data(1, s.charAt(0), null, 0);
  Data maxData = prev;
  int maxEnd = 0;
  for (int i = 1; i < s.length(); i++) {
    Data curr = new Data();
    Character charAtI = s.charAt(i);
    if (charAtI.equals(prev.last) || prev.notLast == null || charAtI.equals(prev.notLast)) {
      curr.len = prev.len + 1;
      curr.notLast = charAtI.equals(prev.last) ? prev.notLast : prev.last;
      curr.last = s.charAt(i);
      curr.m = charAtI.equals(prev.last) ? curr.m : i;
    } else {
      curr.len = i - prev.m + 1;
      curr.notLast = prev.last;
      curr.last = s.charAt(i);
      curr.m = i;
    }
    if (curr.len > maxData.len) {
      maxData = curr;
      maxEnd = i;
    }
    prev = curr;
  }
  String result = s.substring(maxEnd - maxData.len + 1, maxEnd + 1);
  return result;
}
Advertisements
Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: