Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Strings

First Non-Repeating Character

Easy · Strings · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Print the first character of the string that appears exactly once, or -1 if every character repeats.

Input

One string s (lowercase letters).

Output

The character, or -1.

Constraints

Example 1

Input

leetcode

Output

l

Example 2

Input

aabb

Output

-1

Hints

  1. First count how often every letter appears.
  2. Then scan the string again from the left and return the first letter whose count is 1.

Approach

Two passes. The first fills a 26-slot frequency array. The second walks the string in its original order and stops at the first character with frequency 1. If none is found, print -1.

Complexity: O(n) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt[26] = {0};
    for (char c : s) cnt[c - 'a']++;
    for (char c : s)
        if (cnt[c - 'a'] == 1) {
            cout << c << "\n";
            return 0;
        }
    cout << -1 << "\n";
    return 0;
}

Python solution

from collections import Counter

s = input().strip()
cnt = Counter(s)
print(next((c for c in s if cnt[c] == 1), -1))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        for (char c : s.toCharArray())
            if (cnt[c - 'a'] == 1) {
                System.out.println(c);
                return;
            }
        System.out.println(-1);
    }
}

Solve First Non-Repeating Character online · All practice problems