- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 53 lines of Python from the credited upstream file abc299_c.py.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4from typing import List5 6 7def run_length_encoding(iterable: list) -> List[list]:8 '''9 Args:10 iterable: A list of numbers or strings.11 Returns:12 A list containing consecutive characters and their count.13 See:14 https:qiita.com/DaikiSuyama/items/07e237b7372e7c7b343215 '''16 17 from itertools import groupby18 19 results = [[key, len(list(group))] for key, group in groupby(iterable)]20 21 return results22 23 24def main():25 import sys26 27 input = sys.stdin.readline28 29 n = int(input())30 s = list(input().rstrip())31 t = run_length_encoding(s)32 33 if t[0][0] == "o":34 t = [['-', 0]] + t35 n += 136 37 if t[-1][0] == "o":38 t = t + [['-', 0]]39 n += 140 41 ans = -142 43 for i, (si, count) in enumerate(t):44 if si == "o":45 if t[i - 1][1] >= 1 or t[i + 1][1] >= 1:46 ans = max(ans, count)47 48 print(ans)49 50 51if __name__ == "__main__":52 main()53