What is the time complexity of First Unique Character in a String?

The optimal solution has a time complexity of O(n).

What data structures are used to solve First Unique Character in a String?

This problem uses Hash Table, String, Queue, Counting. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving First Unique Character in a String?

Insight 1: We need to keep track of the frequency of each character in the string. Insight 2: A hash table (or an array due to the constraint on character set) is suitable for storing the character counts.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

First Unique Character in a String - LeetCode 387 Solution

Q: How to solve First Unique Character in a String?

The solution involves using a hash table (or array for C) to count the occurrences of each character in the string. After counting the occurrences, we iterate through the string again. In this second pass, we check the count of each character. The first character encountered with a count of 1 is the first unique character, and its index is returned. If no character has a count of 1 after the second pass, it means no unique character exists, so -1 is returned.

Q: Which companies ask LeetCode 387. First Unique Character in a String in interviews?

This problem is frequently asked at EPAM Systems, Goldman Sachs, Ozon, PayPal, Qualcomm and 5 more companies.

First Unique Character in a String - Complete Solution Guide

First Unique Character in a String is LeetCode problem 387, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a string s , find the first non-repeating character in it and return its index. If it does not exist, return -1 . Example 1: Input: s = "leetcode" Output: 0 Explanation: The character 'l' at index 0 is the first character that does not occur at any other index. Example 2: Input: s = "loveleetcode" Output: 2 Example 3: Input: s = "aabb" Output: -1 Constraints: 1 <= s.length <= 10 5 s consists of only lowercase English letters.

Detailed Explanation

The problem asks us to find the index of the first character in a given string that appears only once. If no such character exists, we should return -1. The string will only contain lowercase English letters, and its length will be between 1 and 100,000 characters inclusive. This means we can use a frequency counting approach efficiently.

Solution Approach

The solution involves using a hash table (or array for C) to count the occurrences of each character in the string. After counting the occurrences, we iterate through the string again. In this second pass, we check the count of each character. The first character encountered with a count of 1 is the first unique character, and its index is returned. If no character has a count of 1 after the second pass, it means no unique character exists, so -1 is returned.

Step-by-Step Algorithm

Step 1: Initialize a hash table (or array) to store character counts. The keys are the characters and the values are their frequencies.
Step 2: Iterate through the input string `s`. For each character, increment its count in the hash table.
Step 3: Iterate through the input string `s` again. For each character at index `i`, check its count in the hash table.
Step 4: If the count of the character at index `i` is 1, return `i`.
Step 5: If the loop completes without finding any character with a count of 1, return -1.

Key Insights

Insight 1: We need to keep track of the frequency of each character in the string.
Insight 2: A hash table (or an array due to the constraint on character set) is suitable for storing the character counts.
Insight 3: We need to iterate through the string twice. The first time to count character frequencies, and the second time to find the first character with a frequency of 1.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Hash Table, String, Queue, Counting.

Companies

Asked at: EPAM Systems, Goldman Sachs, Ozon, PayPal, Qualcomm, ServiceNow, Walmart Labs, Yandex, Zoho, tcs.

First Unique Character in a String | LeetCode 387

Easy

Hash Table String Queue Counting

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (charCount.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 387: First Unique Character in a String - Detailed explanation and solution approaches.

Topics

Hash Table String Queue Counting

Companies

EPAM SystemsGoldman SachsOzonPayPalQualcommServiceNowWalmart LabsYandex

Stats

Difficulty:Easy

Languages:4

Companies:10

Problem #:387

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize a hash table (or array) to store character counts. The keys are the characters and the values are their frequencies.
2
Step 2: Iterate through the input string `s`. For each character, increment its count in the hash table.
3
Step 3: Iterate through the input string `s` again. For each character at index `i`, check its count in the hash table.
4
Step 4: If the count of the character at index `i` is 1, return `i`.
5
Step 5: If the loop completes without finding any character with a count of 1, return -1.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is derived from the two iterations over the string `s`. The space complexity is determined by the maximum number of distinct characters we need to store in our frequency counter, which is limited to 26 because of the constraint of lowercase English letters. Therefore, the space used does not scale with the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using `collections.Counter` in Python

Python's `collections.Counter` provides a more concise way to count character frequencies. The rest of the algorithm remains the same.

Time: O(n)Space: O(1)

Trade-offs: More readable in Python, but essentially does the same thing as the manual counting approach. No performance benefits.

✨

Key Insights

1Insight 1: We need to keep track of the frequency of each character in the string.
2Insight 2: A hash table (or an array due to the constraint on character set) is suitable for storing the character counts.
3Insight 3: We need to iterate through the string twice. The first time to count character frequencies, and the second time to find the first character with a frequency of 1.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Queue

FIFO structure - First In, First Out. Like a line at a store!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string. The problem states the string length is between 1 and 10^5, therefore the edge case of empty string does not need to be considered, although a good implementation would also handle that gracefully and return -1.
Edge case 2: String with all repeating characters, like 'aabb'. The solution correctly returns -1 in this case because no character will have a count of 1.
Edge case 3: String with a single character, like 'a'. The solution correctly returns 0 in this case because 'a' appears once and is the first character.
Edge case 4: Long strings with large amount of characters, like a string with 10^5 characters. The solution holds because the time complexity is linear.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Prematurely returning the first character encountered without checking if it's actually unique. This would lead to incorrect results when the first character is repeated later in the string.

✗Common mistake 2: Not handling the case where no unique character exists, resulting in incorrect or unexpected output. Forgetting to return -1.

✗Common mistake 3: Inefficiently iterating through the string multiple times unnecessarily (e.g., using nested loops), leading to a higher time complexity.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing text data to identify unique keywords or phrases, for example, in search engine optimization (SEO) or sentiment analysis.

🏦Real-world scenario 2: Processing log files or data streams to detect the first occurrence of a specific event or error message that is unique within a certain time window.

🎮Real-world scenario 3: Finding the first non-repeating character in usernames to avoid potential conflicts in a registration system.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 28, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 30

❓

Frequently Asked Questions

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "First Unique Character in a String"?

For this easy-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?