null character in c++ string identifying itself as a space

Question

in the below question, my code prints extra spaces in some cases, and I can't figure out why.

Largest Odd Number in String You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

link: https://leetcode.com/problems/largest-odd-number-in-string/description/

string largestOddNumber(string num) {
    int  i = num.length() - 1;
    while (i >= 0) {
        char I = num[i];
        if ((I == '8' || I == '6' || I == '4' || I == '2' || I == '0')) {
            i--;
        }
        else {
            num[i + 1] = '\0';
            //cout<< num[i+1] ;
            return num;
        }
    }
    return "";
}

this is the function i wrote but in the case "52" it is giving the output "5 " isn't null character supposed to terminate the string? where is the extra space coming from?

Edit: Thanks everyone for the answers, understood my mistake and the conceptual error.

`'\0'` terminates a C-style zero-terminated string, one that is a `char *`. A C++ `std::string` is allowed to contain null characters. If you want to change the length, then change the length with `resize`. — Tim Roberts, Aug 11 '23 at 04:11
if a c++ string can contain '\0' so does the compiler reads it as a space or a seperate character? — Shorya, Aug 11 '23 at 04:14
print out the result of `num.length()-1` when you have an empty string, you'll see the problem — NathanOliver, Aug 11 '23 at 04:16
You may find it interesting to read: [Can a std::string contain embedded nulls?](https://stackoverflow.com/q/2845769/1563833). (Spoiler: _yes_ it can.) Writing a `'\0'` to `num[i + 1]` does **not** truncate the string at that position, rather it embeds a NUL character into the string. You may prefer to `return num.substr(0, i + 1);` — Wyck, Aug 11 '23 at 04:31
The compiler does not read it as a space, but in your case, it's not the compiler doing the reading. It's YOU, the human. It depends on how you output it. If you display that string in a font that does not contain a glyph for 0, you'll see a space. — Tim Roberts, Aug 11 '23 at 04:45
Consider using `std::string_view` for both the function parameter and the return value, since there's no need to copy the string. — paddy, Aug 11 '23 at 04:59
@paddy I don't know if changing the return type will make a big difference in the context of leetcode. The return type they provide is `std::string`, if you return a `std::string_view`, it will still be used to construct a `std::string`. Probably better to then just return a `std::string` directly. I do agree with changing the parameter to a `std::string_view`. — sweenish, Aug 11 '23 at 05:31
Oh, right. I didn't even see the bit about leetcode. My eyes probably glazed over. Was making a general comment about the code itself. — paddy, Aug 11 '23 at 05:37
If the largest number is the entire string, writing to `num[i+1]` is undefined. Use `substr`. — molbdnilo, Aug 11 '23 at 09:29

sweenish · Answer 1 · 2023-08-11T06:14:05.063

As pointed out in comments, the biggest issue here is the misconception that a std::string is merely a simple wrapper around a C-string. The issue is the idea that inserting a null character will terminate your string for you. A simple demo:

#include <iostream>
#include <string>

int main() {
  std::string num{"123456789"};
  num[4] = '\0';  // Overwriting the 5
  std::cout << num << '\n';
}

Output:

// The '\0' didn't end the string, it just disappeared the 5
12346789

So, we've shown that the null character tactic won't work. Let's instead return a new string.

class Solution {
public:
    std::string largestOddNumber(std::string_view num) {
      for (int i = num.length() - 1; i >= 0; --i) {
        if ((num[i] - '0') & 1) {
          return std::string(num.begin(), num.begin() + i + 1);
        }
      }
      // If the loop ends naturally, we never found an odd number
      return "";
    }
};

The results are:
Runtime: 22ms (beats 83.83%)
Memory: 13.7MB (beats 99.76%)

I haven't looked at the posted solutions, but I'm satisfied with the results. I may take a gander because I enjoy learning about some of these algorithms and the various ways they can be applied.

A big time-save for determining if a value is odd is the bitwise AND with 1. If there's a faster way, I don't know it. And I'm not being facetious; if someone knows a faster way then I am happy to learn. But any human-readable binary representation of an odd number will have the rightmost bit set to 1. It's one comparison versus the five in your code. If I find an odd number, I return a newly constructed string from the beginning of num to where the odd number was found.

I also changed the parameter type to std::string_view. It's much more efficient when passing a read-only string around. Changin the return type to std::string_view would make a lot of sense outside of leetcode, but since they were expecting a std::string, it would have just been an extra type conversion. So I avoided it.

Edit: I took a look. A few solutions modify num directly by popping off the last character if it's even and eventually returning num directly. In one attempt, it ran slower by about 5ms and consumed a tiny amount (0.09MB) more RAM. But, if I submitted a few times, I'd probably get runtimes similar to my original result. But why bother when I have my original result?

Looking further, I'm surprised that code using modulo operators is faster than mine. I guess the "new-fangled" CPUs can now do it intrinsically. One of the fastest solutions just did a bunch of hacky garbage, and I wouldn't bother with any of that unless performance above all else was the goal.

score 0 · Answer 2 · answered Aug 11 '23 at 05:27

0

The answer from https://stackoverflow.com/a/11752711/22373155 suggests that \0 in std::string does not terminate the string. If you add more even numbers after 2, you can recreate the issue. An alternative would be to return a slice of the string with return num.substr(0,i+1).

answered Aug 11 '23 at 05:27

Tanmay

1
1

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Shawn Aug 14 '23 at 08:23

null character in c++ string identifying itself as a space

2 Answers2