Capitalize First and Last Character of Each Word

14
0

Given a string s with one or more words separated by single spaces, uppercase the first and last letters of each word. For a word with one letter, uppercase that letter once. Return the transformed string.

Example 1

Input: s = "hello world a test"

Output: "HellO WorlD A TesT"

Explanation: The ends of hello, world, and test become uppercase. The word a has just one letter, so it becomes A.

Example 2

Input: s = "q"

Output: "Q"

Explanation: The letter q is both the first and last letter of the only word.

Approach

A space marks the end of a word, and the end of the string marks the boundary of the final word. The letter just before a boundary is the last letter of that word. Its first letter follows the previous space or starts the string. These two positions coincide for a one-letter word.

Every word ends at exactly one of these boundaries, so a single scan reaches every pair of ends. A string can contain a one-letter word at every other position. If those letters are lowercase, each requires an update, so linear time is optimal.

Algorithm

  • Mark the beginning of the string as the start of the first word.

  • Scan from left to right and treat the position just past the final letter as a boundary.

  • At each space or end boundary, locate the first letter at the saved word start and the last letter immediately before the boundary.

  • Uppercase both letters when they occupy different positions. Uppercase the letter once when the positions coincide, including for a one-letter input.

  • Move the saved word start to the position after the boundary.

  • Return the transformed string after processing the final boundary.

Dry Run

Capitalize First and Last Character of Each Word

Capitalize First and Last Character of Each Word

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the string with each word's first and last letters capitalized.
string capitalizeFirstLast(string s) {
int start = 0;
int n = s.length();
// Include the position just past the last letter to process the final word.
for (int i = 0; i <= n; i++) {
// A space or the end of the string closes the current word.
if (i == n || s[i] == ' ') {
// A one-letter word has just one position to update.
if (i - start == 1) {
s[start] = toupper(s[start]);
}
// A longer word has separate first and last positions.
else if (i - start > 1) {
s[start] = toupper(s[start]);
s[i - 1] = toupper(s[i - 1]);
}
// The next word starts after the separator.
start = i + 1;
}
}
return s;
}
};
// Driver code
int main() {
// instance for class Solution
Solution sol;
string s = "hello world a test";
cout << sol.capitalizeFirstLast(s) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N) because the scan does constant work per position, and converting between a string and a character buffer also takes linear time.

Space Complexity: The scan uses O(1) extra space beyond its working buffer. Python, Java, and JavaScript allocate an O(N) character buffer. C++ edits its local string directly, and passing an existing string by value can require an O(N) copy.

Interview follow-up Questions

At i = n, the end check is already true. The OR expression then skips the space check, so the code can process the final word without reading past the last letter.

StringTCS NQT

Read Similar Blogs

Comments0