function replace substring returns incorrect answer

I have a program replacing a substring in a string. The idea is to find the string_to_be_replaced in original_string, then realloc the new_string and connect it to replace_by string. It works for some cases but in some cases like below, it return wrong answer:

Input:

abc def ghi //orginal string

(a blank space) //string to be replaced

1234 //replace by

Output:

abc1234defT123ghi

Expected output:

abc1234def1234ghi

When I debug it, I saw a wrong character has been filled in the new_string after the first replacement had been done.

Please tell me why does this happen and how to fix it. Any help would be appreciated.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

void fgetsWithoutNewline(char *s, size_t maxCount, FILE *fp);
bool sameString(char *original_tring, char *string_to_be_searched, size_t start);
char *replaceString(char *original_tring, char *string_to_be_replaced, char *replace_by);

int main()
{
    char *original_string = malloc(100);
    fgetsWithoutNewline(original_string, 99, stdin);

    char *string_to_be_replaced = malloc(100);
    fgetsWithoutNewline(string_to_be_replaced, 99, stdin);

    char *replace_by = malloc(100);
    fgetsWithoutNewline(replace_by, 99, stdin);

    char *s = replaceString(original_string, string_to_be_replaced, replace_by);
    printf("%s", s);

    free(original_string);
    free(string_to_be_replaced);
    free(replace_by);
    return 0;
}

void fgetsWithoutNewline(char *s, size_t maxCount, FILE *fp)
{
    if (fgets(s, maxCount, fp))
    {
        s[strcspn(s, "\n")] = '\0';
    }
    return;
}

char *replaceString(char *original_tring, char *string_to_be_replaced, char *replace_by)
{
    if (!original_tring || !string_to_be_replaced || !replace_by)
    {
        return NULL;
    }
    char *new_string = malloc(strlen(original_tring));

    for (size_t i = 0, j = 0; i < strlen(original_tring); i++, j++)
    {
        if (sameString(original_tring, string_to_be_replaced, i))
        {
            new_string = realloc(new_string, strlen(new_string) + strlen(replace_by) - strlen(string_to_be_replaced));
            strcat(new_string, replace_by);
            i += strlen(string_to_be_replaced) - 1;  // i and j use to track the last character of original string and new string
            j += strlen(replace_by) - 1;
        }
        else
        {
            new_string[j] = original_tring[i];
        }
    }
    return new_string;
}

bool sameString(char *original_tring, char *string_to_be_searched, size_t start)
{
    if (strlen(string_to_be_searched) + start > strlen(original_tring))
    {
        return false;
    }
    size_t end = strlen(string_to_be_searched) + start;
    for (size_t i = start, j = 0; i < end; i++, j++)
    {
        if (original_tring[i] != string_to_be_searched[j])
        {
            return false;
        }
    }
    return true;
}