387. First Unique Character in a String

Задача

Дана строка s. Найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1.

Примеры

Пример 1

Input: s = "leetcode"
Output: 0

Пояснение

Символ ‘l’ на индексе 0 — первый символ, который не встречается на других индексах.

Пример 2

Input: s = "loveleetcode"
Output: 2

Пример 3

Input: s = "aabb"
Output: -1

Решение

Решение

/**
 * Временная сложность: O(N) - два прохода по строке
 * Пространственная сложность: O(1) - так как букв в алфавите всего 26 (константа)
 */
var firstUniqChar = function(s) {
    const count = {};
 
    // 1. Считаем частоты
    for (let char of s) {
        count[char] = (count[char] || 0) + 1;
    }
 
    // 2. Ищем первую единицу
    for (let i = 0; i < s.length; i++) {
        if (count[s[i]] === 1) {
            return i;
        }
    }
 
    return -1;
};

Решение 2 (indexOf + lastIndexOf)

/**
 * Временная сложность: O(N^2) - внутри цикла O(N) вызывается O(N) поиск
 * Пространственная сложность: O(1)
 */
var firstUniqChar = function(s) {
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        // Если первое вхождение совпадает с последним, значит символ уникален
        if (i === s.lastIndexOf(char)) {
            return i;
        }
    }
    return -1;
};

Решение 3 (Array)

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(1) - массив всегда длиной 26
 */
var firstUniqChar = function(s) {
    const freq = new Array(26).fill(0);
    const codeA = 'a'.charCodeAt(0);
 
    // 1. Заполняем массив частот
    for (let i = 0; i < s.length; i++) {
        freq[s.charCodeAt(i) - codeA]++;
    }
 
    // 2. Ищем единицу
    for (let i = 0; i < s.length; i++) {
        if (freq[s.charCodeAt(i) - codeA] === 1) {
            return i;
        }
    }
 
    return -1;
};