Perfect Pairable String — Problem Statement & Solution Guide
Problem Description
You are provided with a string s consisting solely of lowercase English letters. The objective is to verify whether the string qualifies as a 'Perfect Pairable String'. A string is defined as Perfect Pairable if and only if it can be completely decomposed into disjoint pairs of identical characters. In other words, every distinct character present in the string must occur an even number of times. If any character appears an odd number of times, the string cannot be fully paired and is therefore not Perfect Pairable.
Your task is to implement a function that takes the string s as input and returns a boolean value. Return true if the string is Perfect Pairable, and false otherwise. Note that the empty string is considered Perfect Pairable as it contains no unpaired characters.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Perfect Pairable String"
WHY DOES IT MATTER?
Checking parity of frequencies is a classic linear-time pattern that appears in many interview problems, such as finding the unique element in an array of duplicates. Mastering this pattern demonstrates a candidate’s ability to transform a seemingly combinatorial problem into a simple counting problem, which is a valuable skill for large-scale data processing.
OPTIMIZATION CHALLENGE
The key insight is that you only need to know whether each count is even or odd, not the exact count. This allows you to use a single bit per character (or a small integer) instead of storing full counts, reducing space and simplifying the logic.
REAL-WORLD CONNECTION
In distributed systems, ensuring that each node processes an even number of tasks before a checkpoint is analogous to this problem. The system must verify that all tasks are paired for redundancy, similar to checking even counts of characters.
When explaining this in an interview, emphasize the O(n) traversal and the constant alphabet size. Highlight that the solution is both time and space optimal for the given constraints, and that it scales gracefully to very long strings.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to checking the parity of character frequencies in the string. A naive solution might attempt to pair characters by scanning the string repeatedly, leading to O(n^2) time if each character is compared with all others. The optimal paradigm is to use a frequency counter: iterate once over the string, increment a count for each character, and then verify that every count is even. Since the alphabet is fixed (26 lowercase letters), the space overhead is O(1) and the time complexity is linear, O(n). This approach guarantees correctness regardless of string length and avoids the combinatorial explosion of naive pairwise comparisons.
Interview Questions on This Problem
Q1How would you determine if a string can be partitioned into pairs of identical characters in an interview setting?
I would explain that the problem is equivalent to checking whether each character appears an even number of times. I would then describe a single-pass frequency count using an array of size 26, followed by a parity check for each count.
Q2A fintech company asks: "What is the time and space complexity of your solution for checking a perfect pairable string?"
The time complexity is O(n), where n is the length of the string, because we traverse the string once. The space complexity is O(1) because we use a fixed-size array of 26 integers regardless of input size.
Q3During a startup interview, you are asked: "Can you optimize the solution further if the alphabet size were not fixed?"
If the alphabet were large or dynamic, we could use a hash map to store counts, maintaining O(n) time and O(k) space where k is the number of distinct characters. For very large alphabets, a bitset or Bloom filter could be used to reduce space at the cost of occasional false positives, but for exact parity checks a hash map remains the most reliable.
Examples
Input
s = "aabbcc"
Output
true
Explanation: Count the frequency of each character: 'a' appears 2 times, 'b' appears 2 times, 'c' appears 2 times. Since all counts are even, the string can be partitioned into pairs ('aa', 'bb', 'cc'). Thus, it is Perfect Pairable.
Input
s = "aabbc"
Output
false
Explanation: Count the frequency of each character: 'a' appears 2 times, 'b' appears 2 times, 'c' appears 1 time. The character 'c' has an odd count (1), meaning it cannot form a complete pair. Therefore, the string is not Perfect Pairable.
Input
s = "zzzz"
Output
true
Explanation: Count the frequency of each character: 'z' appears 4 times. Since 4 is an even number, the characters can be grouped into two pairs ('zz', 'zz'). The string is Perfect Pairable.
Input
s = "ab"
Output
false
Explanation: Count the frequency of each character: 'a' appears 1 time, 'b' appears 1 time. Both counts are odd. Neither character can form a pair with an identical character. The string is not Perfect Pairable.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters only
- Time complexity should be O(n) where n is the length of the string
- Space complexity should be O(1) or O(k) where k is the number of distinct characters
Optimal Approach & Strategy
The optimal solution counts character frequencies in a single pass and then checks parity, achieving O(n) time and O(1) space. This leverages the fixed alphabet size to keep space constant.
Brute Force Approach
A naive approach would try to pair each character with another by scanning the string for matches, leading to O(n^2) time. It would also require repeatedly removing matched pairs, which is inefficient for long strings.
Verified Code Solutions
const fs = require('fs');\nconst input = fs.readFileSync(0, 'utf8').trim();\nlet s = input;\nconst cnt = new Array(26).fill(0);\nfor (const ch of s) cnt[ch.charCodeAt(0) - 97]++;\nlet ok = true;\nfor (const x of cnt) if (x % 2 !== 0) { ok = false; break; }\nconsole.log(ok ? "true" : "false");#include <bits/stdc++.h>\nusing namespace std;\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n string s;\n if (!(cin >> s)) return 0;\n vector<int> cnt(26, 0);\n for (char c : s) cnt[c - 'a']++;\n bool ok = true;\n for (int x : cnt) if (x % 2 != 0) { ok = false; break; }\n cout << (ok ? "true" : "false");\n return 0;\n}import java.io.*;\nimport java.util.*;\n\npublic class Main {\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n String s = br.readLine();\n int[] cnt = new int[26];\n for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;\n boolean ok = true;\n for (int x : cnt) if (x % 2 != 0) { ok = false; break; }\n System.out.println(ok ? "true" : "false");\n }\n}import sys\ns = sys.stdin.readline().strip()\ncnt = [0] * 26\nfor ch in s:\n cnt[ord(ch) - 97] += 1\nok = all(x % 2 == 0 for x in cnt)\nprint("true" if ok else "false")const fs = require('fs');\nconst input = fs.readFileSync(0, 'utf8').trim();\nlet s = input;\nconst cnt = new Array(26).fill(0);\nfor (const ch of s) cnt[ch.charCodeAt(0) - 97]++;\nlet ok = true;\nfor (const x of cnt) if (x % 2 !== 0) { ok = false; break; }\nconsole.log(ok ? "true" : "false");Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.