Day 4 - Non Repeating Character.md

Difficulty	Source	Tags
Easy	160 Days of Problem Solving	Strings Hash

🚀 Day 4. Non-Repeating Character 🧠

The problem can be found at the following link: Problem Link

💡 Problem Breakdown:

Given a string s consisting of lowercase Latin letters, return the first non-repeating character in s. If there is no non-repeating character, return '$'.

Note: When you return '$', the driver code will output -1.

🔍 Example Walkthrough:

Input:
s = "geeksforgeeks"
Output:
'f'

Explanation:
In the given string, 'f' is the first character in the string which does not repeat.

Input:
s = "racecar"
Output:
'e'

Explanation:
In the given string, 'e' is the only character in the string which does not repeat.

Input:
s = "aabbccc"
Output:
-1

Explanation:
All the characters in the given string are repeating.

Constraints:

• $1 <= s.size() <= 10^5$

🎯 My Approach:

1. Frequency Array Method:

   • Since the input consists only of lowercase Latin letters, a frequency array of size 26 is sufficient to count occurrences of each character.
   • Traverse the string once to update the frequency of each character in the array.
   • Traverse the string a second time to identify the first character with a frequency of 1.

2. Steps:

   • Initialize a frequency array freq[26] and set all elements to 0.
   • For each character in the string, increment its corresponding frequency in the array.
   • Iterate through the string again, checking for the first character with a frequency of 1.
   • If no such character exists, return '$'.

🕒 Time Complexity:

• Expected Time Complexity: O(n), where n is the size of the string. The algorithm requires two linear passes through the string.
• Expected Auxiliary Space Complexity: O(1), as the frequency array uses a fixed amount of additional space (26 elements).

📝 Solution Code

Code (C)

char nonRepeatingChar(char s[]) {
    int freq[26] = {0};  
    for (int i = 0; s[i] != '\0'; i++) {
        freq[s[i] - 'a']++;
    }
    for (int i = 0; s[i] != '\0'; i++) {
        if (freq[s[i] - 'a'] == 1) {
            return s[i];
        }
    }
    return '$';
}

Code (Cpp)

class Solution {
public:
    char nonRepeatingChar(string &s) {
        int freq[26] = {0};  
        for (char c : s) {
            freq[c - 'a']++;
        }
        for (char c : s) {
            if (freq[c - 'a'] == 1) {
                return c;
            }
        }
        return '$';
    }
};

👨‍💻 Alternative Approaches

class Solution {
public:
    char nonRepeatingChar(string &s) {
        unordered_map<char, int> freq;

        for (char c : s) {
            freq[c]++;
        }
        for (char c : s) {
            if (freq[c] == 1) {
                return c;
            }
        }
        return '$';
    }
};

Code (Java)

class Solution {
    static char nonRepeatingChar(String s) {
        int[] freq = new int[26];  
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        for (char c : s.toCharArray()) {
            if (freq[c - 'a'] == 1) {
                return c;
            }
        }
        return '$';
    }
}

Code (Python)

class Solution:
    def nonRepeatingChar(self, s):
        freq = [0] * 26  
        for c in s:
            freq[ord(c) - ord('a')] += 1
        for c in s:
            if freq[ord(c) - ord('a')] == 1:
                return c
        return '$'

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count