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
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 codeint 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".
Be the first to add a comment.