仍然是双指针,维护一个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