Skip to content

Instantly share code, notes, and snippets.

@billyeh
Created August 1, 2020 01:23
Show Gist options
  • Save billyeh/45db780f54c4beb7680dcd9046ac2c11 to your computer and use it in GitHub Desktop.
Save billyeh/45db780f54c4beb7680dcd9046ac2c11 to your computer and use it in GitHub Desktop.
from typing import Iterable, Optional, Tuple
import unittest
def longest_substring_with_two_characters(s: str) -> Optional[Tuple[int]]:
"""Finds the longest substring in s that contains up to 2 distinct characters."""
substring_start = 0
current_index = 0
other_char = None
continuous_substring_start = 0
ret = (0, 0)
while current_index < len(s):
current_letter = s[current_index]
if current_letter != s[substring_start]:
if other_char is None:
other_char = current_letter
if current_letter != other_char:
ret = max(ret, (current_index - substring_start, substring_start))
substring_start = continuous_substring_start
other_char = current_letter
continuous_substring_start = current_index
if current_letter != s[continuous_substring_start]:
continuous_substring_start = current_index
current_index += 1
return max(ret, (current_index - substring_start, substring_start))[::-1]
class InterviewTestCase(unittest.TestCase):
def testLongestSubstringWithTwoCharacters(self):
self.assertEqual(longest_substring_with_two_characters('aabbcccdd'), (4, 5))
self.assertEqual(longest_substring_with_two_characters('aaaa'), (0, 4))
self.assertEqual(longest_substring_with_two_characters(''), (0, 0))
self.assertEqual(
longest_substring_with_two_characters('aaabcabbcbccd'), (6, 6))
self.assertEqual(longest_substring_with_two_characters('abababab'), (0, 8))
if __name__ == '__main__':
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment