CF 59A - Word
The task is to normalize the case of a single word so that either all letters are lowercase or all are uppercase.
Rating: 800
Tags: implementation, strings
Solve time: 1m 11s
Verified: yes
Solution
Problem Understanding
The task is to normalize the case of a single word so that either all letters are lowercase or all are uppercase. The decision depends on which case dominates in the input: if there are more uppercase letters than lowercase letters, the word should be transformed entirely to uppercase; otherwise, it should be converted entirely to lowercase. If the counts are exactly equal, lowercase is preferred.
The input is a single word containing only English letters, with a length between 1 and 100 characters. This length is small, so we can afford to iterate through all characters multiple times without worrying about efficiency. No complex data structures or sorting is needed.
Edge cases include words that are already uniform in case, a single-letter word, and words where the counts of uppercase and lowercase letters are exactly equal. For example, the input "a" should remain "a", and "Ab" should become "ab" because lowercase ties are broken in favor of lowercase. A naive implementation might forget to handle the tie condition correctly or might miscount letters by not distinguishing strictly between uppercase and lowercase.
Approaches
A brute-force approach would scan the string and, for each letter, check if it is uppercase or lowercase and maintain separate counters. Then, after counting, compare the totals and convert the word accordingly. This approach is actually efficient enough for our constraints, because the word has at most 100 characters and each operation is O(1). So, even a double scan-one for counting and one for conversion-is acceptable.
The key observation that simplifies the implementation is that Python provides built-in string methods to check case (isupper()) and convert entire strings to a specific case (upper() and lower()). We do not need to track individual indices for conversion because the conversion applies to the whole string.
The difference between brute-force and optimal is mostly stylistic here. The optimal approach is simply a single linear scan to count uppercase letters, then a conditional application of upper() or lower() to the entire string. There is no need for a more complicated structure.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force (count + convert) | O(n) | O(1) | Accepted |
| Optimal (count uppercase, convert once) | O(n) | O(1) | Accepted |
Algorithm Walkthrough
- Initialize a counter for uppercase letters. This is the minimal state needed to decide the final transformation.
- Iterate over each character in the input word. For every character, check if it is uppercase using the standard language method. Increment the uppercase counter if it is. We do not need a lowercase counter because the total length minus the uppercase count gives the lowercase count.
- After scanning all letters, compare the uppercase count to the lowercase count (computed as total length minus uppercase count). If the uppercase count is strictly greater, convert the entire word to uppercase. Otherwise, convert the entire word to lowercase.
- Print the transformed word.
Why it works: at step 3, the comparison ensures that the minimal number of letter transformations is applied. If uppercase dominates, converting all to uppercase changes fewer letters than converting to lowercase. If lowercase dominates or they tie, converting to lowercase achieves the same minimal-change goal. The invariant is that at the moment of conversion, we already know the global majority case, so no local miscalculations can occur.
Python Solution
import sys
input = sys.stdin.readline
word = input().strip()
uppercase_count = sum(1 for c in word if c.isupper())
lowercase_count = len(word) - uppercase_count
if uppercase_count > lowercase_count:
print(word.upper())
else:
print(word.lower())
The first line reads the input efficiently. Using strip() removes any trailing newline. The comprehension sum(1 for c in word if c.isupper()) counts uppercase letters in a single pass. The lowercase count is computed as the difference between total length and uppercase count, avoiding a second iteration. The conditional applies the correct transformation in one step.
Subtle points: forgetting to strip() would leave a trailing newline in the output. Miscounting uppercase vs lowercase or using >= instead of > would violate the tie-breaking rule.
Worked Examples
Example 1
Input: "HoUse"
| Step | Uppercase Count | Lowercase Count | Decision | Output |
|---|---|---|---|---|
| Count letters | 2 (H, U) |
3 (o, s, e) |
lowercase dominates | house |
This confirms the algorithm correctly chooses lowercase when it is in the majority.
Example 2
Input: "ViP"
| Step | Uppercase Count | Lowercase Count | Decision | Output |
|---|---|---|---|---|
| Count letters | 2 (V, P) |
1 (i) |
uppercase dominates | VIP |
This demonstrates correct handling when uppercase letters are more frequent.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | We scan the string once to count and then apply a single conversion operation. Each step is linear in word length. |
| Space | O(1) | Only two counters and a few temporary references are used. The output string shares memory with the input in Python implementation. |
With n ≤ 100, this solution runs instantly and requires negligible memory.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
word = sys.stdin.readline().strip()
uppercase_count = sum(1 for c in word if c.isupper())
lowercase_count = len(word) - uppercase_count
return word.upper() if uppercase_count > lowercase_count else word.lower()
# provided sample
assert run("HoUse\n") == "house", "sample 1"
# all lowercase
assert run("abcde\n") == "abcde", "all lowercase"
# all uppercase
assert run("ABCDE\n") == "ABCDE", "all uppercase"
# tie case
assert run("Ab\n") == "ab", "tie case -> lowercase"
# single character uppercase
assert run("X\n") == "X", "single uppercase"
# single character lowercase
assert run("x\n") == "x", "single lowercase"
# mixed with more uppercase
assert run("PyTHon\n") == "PYTHON", "more uppercase"
| Test input | Expected output | What it validates |
|---|---|---|
| HoUse | house | lowercase majority |
| abcde | abcde | all lowercase input |
| ABCDE | ABCDE | all uppercase input |
| Ab | ab | tie handled correctly |
| X | X | single-letter uppercase |
| x | x | single-letter lowercase |
| PyTHon | PYTHON | more uppercase letters |
Edge Cases
For the tie scenario "Ab", the algorithm computes uppercase_count = 1, lowercase_count = 1. The condition uppercase_count > lowercase_count fails, so the word is converted to lowercase "ab". This correctly applies the rule that ties favor lowercase.
For a single-letter word "X", the uppercase count is 1, lowercase count is 0. The condition is true, so the output remains "X". For "x", the condition is false, and the output remains "x". Both cases confirm the algorithm handles the minimal input size correctly.
This editorial ensures that a reader can reproduce the approach on any similar problem of case normalization or majority-based transformation.