Sunday, January 18, 2015

[LeetCode]Longest Substring with At Most Two Distinct Characters


仍然是双指针,维护一个map,这里substring只允许最多两个distinct characters,左指针根据右指针移动的策略是:

  • 若右指针指向的字符在map内,更新map,看有没需要更新返回的substring
  • 若右指针指向的字符不在map里,更新map,如果map的size小于等于2,看有没需要更新返回的substring
  • 若右指针指向的字符不在map里,更新map,如果map的size大于2,右移左指针直到map的size小于等于2,看有没需要更新返回的substring
时间复杂度是O(n),代码如下:

No comments:

Post a Comment