# LeetCode Easy 387. First Unique Character in a String

tags: leetcode

C++よりもRustの方が書いていて楽しいのでRustで書けそうな問題はRustで書いていくことにします．

(コーディングインタビューで使われる程度のC++の文法ならば，普段から使っていなくてもなんとかなると楽観視しています)

問題

• Explore
• Problems

アイデア

文字列ないで反復しない最初の文字のindexを返せという問題です．

複数回出たかどうかは連想配列を用いれば簡単に計算できます．

解法

• まずは配列，<character, index>という風に記録する連想配列を用意します．
• 与えられた文字列を走査します．
  • もし文字が連想配列に記録されていたら配列の値を-1にします．
    • 記録されていなかったら，配列のその文字列が記録されいる部分を-1にします．
    • <character, index>という風にして，連想配列に記録します．
• 最後に配列の中を見ます．
  • -1以外ならば，答えの変数と比較して小さい場合は更新します．

計算量

文字列の長さを$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Rust

use std::collections::HashMap;

impl Solution {
  pub fn first_uniq_char(s: String) -> i32 {
    let mut seen = HashMap::new();
    let mut res = vec![];

    for (i, c) in s.chars().enumerate() {
      if let Some(&i) = seen.get(&c) {
        res[i] = -1;
      } else {
        res.push(i as i32);
        seen.insert(c, res.len() - 1);
      }
    }

    for idx in res {
      if idx != -1 {
        return idx;
      }
    }
    return -1;
  }
}