Excellent point! This solution doesn't, and fails tests where over/under flow is a concern.

Filtering entries that may cause issues with s-i then allows the original algorithm to work.

Not entirely sure where you're getting O(n^2) from. Size is O(1), sort is O(nlogn) and array lookup is O(1).

Although, even with this miscalculation, you'd be right in asserting that O(n) solutions do exist.

I am unsure if you have fixed you issue or not, but when I attempt to run your code, I get this: no viable conversion from 'std::string' (aka 'basic_string') to 'pair<std::string, std::string>' (aka 'pair<basic_string, basic_string >')
pair<string,string> actual = capitalize(s);

Why?

The reason for this is because your function, which you have named capitalize; does not match it's output with what the test requires. The test requires an output of std::pair<std::string, std::string>, not simple an std::string.

Yeah that's my bad. Sorry.

Chars can be interpretted as arrays when doing arithmetic. Thus when you're attempting to sum digits as chars together, you're summing the integer value of the characters, not the actual digits. - '0' subtracts the int value of '0' from the int value of the character being popped, giving you the actual value you want as an integer.