Find Non-Repeating Characters in a String

6
0

Given a string s, return all characters that appear exactly once, in their original order, as a comma-separated string. If no such characters exist, return an empty string "".

Example 1

Input: s = "balloon"

Output: "b,a,n"

Explanation: The characters b, a, and n appear exactly once, in that order.

Example 2

Input: s = "aabbcc"

Output: ""

Explanation: Every character appears twice, so there are no non-repeating characters.

Approach

A character is non-repeating only if it appears once in the entire string. Seeing a character for the first time does not confirm this, because it might appear again later. First, count how many times each character appears. A hash map stores these counts, mapping each character to its number of occurrences.

Once the counts are ready, read the original string again from left to right. Keep a character only when its total count is exactly one. Reading the string in this order keeps the selected characters in their original order.

Finally, place commas between the selected characters. There should be no comma before the first character or after the last. If nothing is selected, the result is an empty string.

Algorithm

  • Scan the string and record the frequency of every character using a hash map.

  • Read the string again from left to right.

  • Select each character whose frequency is exactly one.

  • Join the selected characters with commas between them.

  • Return the resulting string, or "" if no characters were selected.

Dry Run

Find non-repeating characters in a string

Find non-repeating characters in a string

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns characters that occur exactly once, separated by commas.
string findNonRepeatingCharacters(const string& s) {
unordered_map<char, int> frequency;
// Count every character across the entire string.
for (char ch : s) {
frequency[ch]++;
}
string result;
// Reading the original string again preserves its order.
for (char ch : s) {
if (frequency[ch] == 1) {
// Add a comma only when a selected character already exists.
if (!result.empty()) {
result += ',';
}
result += ch;
}
}
return result;
}
};
// Driver code
int main() {
string s = "balloon";
// Create an instance of Solution.
Solution sol;
cout << sol.findNonRepeatingCharacters(s) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N) expected time, where N is the string length. The string is scanned twice, and hash-map updates and lookups take expected O(1) time.

Space Complexity: O(D + R), where D is the number of distinct characters and R is the number of selected characters. This includes the frequency map and storage used to build the result, and is at most O(N).

Interview follow-up Questions

Yes. For example, in "AaA", uppercase A appears twice, while lowercase a appears once. The result is "a".

StringHashingTCS NQT

Read Similar Blogs

Comments0