Longest Substring Without Repeating Characters

与えられた文字列に対して、重複しない最長の部分文字列の長さを返す問題。Greedy Algorithmで解くことができる。

部分文字列の開始の文字を変数として保存し、Iterateしていく中で重複した文字と遭遇した際に開始位置を更新することで最長の文字列を算出する。 注意点としてはindexが0ベースなので最長文字列を計算する際に+1する、そしてスタート位置を更新する際は重複している次のindexを指定する。

pub fn length_of_longest_substring(s: String) -> i32 {
    let mut last_index = HashMap::new();
    let mut ans = 0;
    let mut start = 0;

    for (i, c) in s.chars().enumerate() {
        if let Some(&j) = last_index.get(&c) {
            start = max(start, j + 1);
        }
        ans = max(ans, i - start + 1);
        last_index.insert(c, i);
    }

    ans as i32
}