Find the first non-repeating character in a string
💡 Concept: First Non-Repeating Character
Identify the first character in a string that does not repeat elsewhere.
📘 Quick Intro
This problem helps understand character frequency analysis and string traversal techniques.
🧠 Analogy
Like finding the unique guest at a party who hasn’t come with a group.
🔧 Technical Explanation
- Traverse string and count frequency of each character.
- Traverse again to find the first character with frequency 1.
- Use dictionary or array for frequency counting.
- Return the character or indication if none found.
- Efficiently handles large strings.
🎯 Use Cases
- ✅ Coding interviews.
- ✅ Text analysis.
- ✅ Detecting unique identifiers.
- ✅ Understanding hashing and dictionaries.
💻 Code Example
public static char? FirstNonRepeatingChar(string input) {
var counts = new Dictionary<char, int>();
foreach (var c in input) {
counts[c] = counts.ContainsKey(c) ? counts[c] + 1 : 1;
}
foreach (var c in input) {
if (counts[c] == 1) return c;
}
return null;
}
❓ Interview Q&A
Q1: What data structure is best for frequency counting?
A: Dictionary or hash map.
Q2: What if no unique character?
A: Return null or special value.
Q3: Time complexity?
A: O(n).
Q4: Can this be optimized?
A: Usually sufficient.
Q5: How to handle case sensitivity?
A: Convert to uniform case.
Q6: Can strings have Unicode?
A: Yes, handle accordingly.
Q7: Why traverse twice?
A: To count then find first unique.
Q8: Is this thread-safe?
A: Yes, for immutable strings.
Q9: Can you return index?
A: Yes, by tracking indexes.
Q10: Alternative approaches?
A: Using queues or ordered dictionaries.
📝 MCQs
Q1. What data structure is best for frequency counting?
- Array
- Dictionary
- List
- Stack
Q2. What if no unique character?
- Throw error
- Return null
- Return first char
- Return last char
Q3. Time complexity?
- O(1)
- O(n)
- O(n^2)
- O(log n)
Q4. Can this be optimized?
- Yes
- No
- Maybe
- Usually sufficient
Q5. How to handle case sensitivity?
- Ignore case
- Convert case
- Use regex
- Use hash
Q6. Can strings have Unicode?
- No
- Yes
- Sometimes
- Rarely
Q7. Why traverse twice?
- Count then find
- Find then count
- One pass
- No traversal
Q8. Is this thread-safe?
- No
- Yes
- Sometimes
- Rarely
Q9. Can you return index?
- No
- Yes
- Sometimes
- Rarely
Q10. Alternative approaches?
- Stacks
- Queues
- Trees
- Graphs
💡 Bonus Insight
This problem helps improve understanding of dictionaries and string traversal patterns.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!