Pythonで指定した時刻の後に来る最も近い回文時刻を見つける方法

問題概要

24時間形式（HH:MM）で時刻を表す文字列 s が与えられます。HH（時）は 0〜23、MM（分）は 0〜59 の範囲に収まります。このとき、文字列として読んだときに回文（前から読んでも後ろから読んでも同じになる文字列）となる、s より後のもっとも近い時刻を求めてください。該当する時刻が存在しない場合は -1 を返します。

たとえば、入力が「22:22」であれば、出力は「23:32」となります。

解法のアプローチ

この問題は、次の手順に従って解くことができます。

• n := 文字列 s の長さ
• hour_string := s の先頭2文字（インデックス 0〜2）を切り出した部分文字列
• minute := s のインデックス 3〜5 の部分文字列を整数に変換したもの
• rev_hour := hour_string を逆順に並べ替えた文字列を整数に変換したもの
• rev_hr_str := hour_string を逆順に並べ替えた文字列
• h := hour_string を整数に変換したもの
• temp := 空文字列、res := 空文字列

そのうえで、以下のように場合分けを行います。

• h が 23 かつ minute が 32 以上の場合：res を -1 とします。
• minute が rev_hour より小さい場合：時（h）はそのままに、分の部分を「時を反転させた数字」に置き換えた時刻が回文になります。
  • h が 10 未満であれば、temp の先頭に「0」を付けます。
  • temp に h を文字列として連結します。
  • rev_hour が 10 未満であれば、res に temp + ":0" + rev_hr_str を連結し、そうでなければ temp + ":" + rev_hr_str を連結します。
• 上記以外の場合：h を 1 増やしてから、同様の処理を実行します。
  • rev_hr_str := h を文字列化して逆順にしたもの
  • rev_hour := rev_hr_str を整数に変換したもの
  • あとは minute < rev_hour の場合と同じ手順で res を組み立てます。
• 最後に res を返します。

考え方のポイント

回文となる時刻「HH:MM」は、分 MM が時 HH を逆から読んだ数字と一致すればよい、という性質を持っています。つまり、候補となる分の値は「時を反転させた値」に限定できるため、1 分ごとにすべての時刻を総当たりで調べる必要がありません。これにより、定数時間で答えを導き出せます。

また、23 時台で分が 32 を超えている場合は、同一日内にもう回文時刻が存在しないため、仕様どおり -1 を返します。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def get_next_palindrome_time(s) :
    n = len(s)
    hour_string = s[0 : 2]
    minute = int(s[3 : 5])
    rev_hour = int(hour_string[::-1])
    rev_hr_str = hour_string[::-1]
    h = int(hour_string)
    temp = ""
    res = ""
    if (h == 23 and minute >= 32) :
        res = "-1"
    elif (minute < rev_hour) :
        if (h < 10) :
            temp = "0"
        temp = temp + str(h)
        if (rev_hour < 10) :
            res = res + temp + ":0" + rev_hr_str
        else :
            res = res + temp + ":" + rev_hr_str
    else :
        h += 1
        rev_hr_str = str(h)[::-1]
        rev_hour = int(rev_hr_str)
        if (h < 10) :
            temp = "0"
        temp = temp + str(h)
        if (rev_hour < 10) :
            res = res + temp + ":0" + rev_hr_str
        else :
            res = res + temp + ":" + rev_hr_str
    return res

s = "22:22"
print(get_next_palindrome_time(s))

入力

"22:22"

出力

23:32

まとめ

このアルゴリズムは、スライスによる文字列反転とシンプルな条件分岐だけで回文時刻を特定できる点が魅力です。総当たり探索が不要なため、時間計算量・空間計算量ともに O(1) となり、非常に効率的です。