First Non-Repeating Character in Stream 🎯

Welcome to another exciting tutorial on CodeYourCraft! Today, we're going to dive into a fascinating problem that involves Data Structures and Algorithms - finding the first non-repeating character in a stream. This problem is quite common in interviews, and it's a great way to understand and practice various data structure concepts. Let's get started! 🎉

Understanding the Problem 📝

Given a stream of characters, write a function that finds and returns the first non-repeating character in the stream. If there are no non-repeating characters, the function should return an empty string (or null, depending on your programming language).

Breaking it Down 💡

To solve this problem, we can create a data structure to keep track of the characters we've seen so far. We will use a HashMap or Dictionary to store the characters as keys and their count as values. As we process the stream, we can check if the character count is equal to 1, indicating it's the first non-repeating character.

Solving the Problem 💻

Let's write a Python solution for this problem.

python

from collections import defaultdict

def first_non_repeating(stream):
    char_count = defaultdict(int)
    for char in stream:
        char_count[char] += 1
        if char_count[char] == 1:
            return char
    return ""

In this Python example, we use a defaultdict to create a frequency map for the characters in the stream. We iterate through the stream, incrementing the count of each character we encounter. If we find a character with a count of 1, we return it as the first non-repeating character. If no such character is found, we return an empty string.

Putting it into Practice 📝

To better understand how this function works, let's consider a few examples:

first_non_repeating("aabbc") should return 'a', as 'a' is the first non-repeating character in the stream.
first_non_repeating("abcabc") should return an empty string, as there are no non-repeating characters in the stream.
first_non_repeating("Mississippi") should return 'M', as 'M' is the first non-repeating character in the stream.

Quiz Time 🎯

Let's test your understanding of the problem and the solution.

Wrapping Up 📝

In this tutorial, we've learned how to find the first non-repeating character in a stream using a Python solution. We've broken down the problem, discussed the approach, and put the solution into practice. By understanding and solving this problem, you've gained valuable experience with Data Structures and Algorithms.

In the next tutorial, we'll explore more interesting problems and deepen our understanding of Data Structures and Algorithms. Until then, happy coding! 🎓💻🚀