diff --git a/Misc/NEWS b/Misc/NEWS
index 106bc9e..9598c3f 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,9 @@
 Core and Builtins
 -----------------
 
+- Issue #29145: Fix overflow checks in string, bytearray and unicode.
+  Patch by jan matejek and Xiang Zhang.
+
 - Issue #28932: Do not include <sys/random.h> if it does not exist.
 
 Extension Modules
diff --git a/Objects/bytearrayobject.c b/Objects/bytearrayobject.c
index 9e3cead..c74ff06 100644
--- a/Objects/bytearrayobject.c
+++ b/Objects/bytearrayobject.c
@@ -1571,31 +1571,30 @@
 {
     char *self_s, *result_s;
     Py_ssize_t self_len, result_len;
-    Py_ssize_t count, i, product;
+    Py_ssize_t count, i;
     PyByteArrayObject *result;
 
     self_len = PyByteArray_GET_SIZE(self);
 
-    /* 1 at the end plus 1 after every character */
-    count = self_len+1;
-    if (maxcount < count)
+    /* 1 at the end plus 1 after every character;
+       count = min(maxcount, self_len + 1) */
+    if (maxcount <= self_len) {
         count = maxcount;
+    }
+    else {
+        /* Can't overflow: self_len + 1 <= maxcount <= PY_SSIZE_T_MAX. */
+        count = self_len + 1;
+    }
 
     /* Check for overflow */
     /*   result_len = count * to_len + self_len; */
-    product = count * to_len;
-    if (product / to_len != count) {
+    assert(count > 0);
+    if (to_len > (PY_SSIZE_T_MAX - self_len) / count) {
         PyErr_SetString(PyExc_OverflowError,
-                        "replace string is too long");
+                        "replace bytes is too long");
         return NULL;
     }
-    result_len = product + self_len;
-    if (result_len < 0) {
-        PyErr_SetString(PyExc_OverflowError,
-                        "replace string is too long");
-        return NULL;
-    }
-
+    result_len = count * to_len + self_len;
     if (! (result = (PyByteArrayObject *)
                      PyByteArray_FromStringAndSize(NULL, result_len)) )
         return NULL;
@@ -1824,7 +1823,7 @@
     char *self_s, *result_s;
     char *start, *next, *end;
     Py_ssize_t self_len, result_len;
-    Py_ssize_t count, product;
+    Py_ssize_t count;
     PyByteArrayObject *result;
 
     self_s = PyByteArray_AS_STRING(self);
@@ -1838,16 +1837,12 @@
 
     /* use the difference between current and new, hence the "-1" */
     /*   result_len = self_len + count * (to_len-1)  */
-    product = count * (to_len-1);
-    if (product / (to_len-1) != count) {
+    assert(count > 0);
+    if (to_len - 1 > (PY_SSIZE_T_MAX - self_len) / count) {
         PyErr_SetString(PyExc_OverflowError, "replace bytes is too long");
         return NULL;
     }
-    result_len = self_len + product;
-    if (result_len < 0) {
-            PyErr_SetString(PyExc_OverflowError, "replace bytes is too long");
-            return NULL;
-    }
+    result_len = self_len + count * (to_len - 1);
 
     if ( (result = (PyByteArrayObject *)
           PyByteArray_FromStringAndSize(NULL, result_len)) == NULL)
@@ -1891,7 +1886,7 @@
     char *self_s, *result_s;
     char *start, *next, *end;
     Py_ssize_t self_len, result_len;
-    Py_ssize_t count, offset, product;
+    Py_ssize_t count, offset;
     PyByteArrayObject *result;
 
     self_s = PyByteArray_AS_STRING(self);
@@ -1908,16 +1903,12 @@
 
     /* Check for overflow */
     /*    result_len = self_len + count * (to_len-from_len) */
-    product = count * (to_len-from_len);
-    if (product / (to_len-from_len) != count) {
+    assert(count > 0);
+    if (to_len - from_len > (PY_SSIZE_T_MAX - self_len) / count) {
         PyErr_SetString(PyExc_OverflowError, "replace bytes is too long");
         return NULL;
     }
-    result_len = self_len + product;
-    if (result_len < 0) {
-        PyErr_SetString(PyExc_OverflowError, "replace bytes is too long");
-        return NULL;
-    }
+    result_len = self_len + count * (to_len - from_len);
 
     if ( (result = (PyByteArrayObject *)
           PyByteArray_FromStringAndSize(NULL, result_len)) == NULL)
diff --git a/Objects/stringobject.c b/Objects/stringobject.c
index 4e38735..9b93898 100644
--- a/Objects/stringobject.c
+++ b/Objects/stringobject.c
@@ -2358,31 +2358,30 @@
 {
     char *self_s, *result_s;
     Py_ssize_t self_len, result_len;
-    Py_ssize_t count, i, product;
+    Py_ssize_t count, i;
     PyStringObject *result;
 
     self_len = PyString_GET_SIZE(self);
 
-    /* 1 at the end plus 1 after every character */
-    count = self_len+1;
-    if (maxcount < count)
+    /* 1 at the end plus 1 after every character;
+       count = min(maxcount, self_len + 1) */
+    if (maxcount <= self_len) {
         count = maxcount;
+    }
+    else {
+        /* Can't overflow: self_len + 1 <= maxcount <= PY_SSIZE_T_MAX. */
+        count = self_len + 1;
+    }
 
     /* Check for overflow */
     /*   result_len = count * to_len + self_len; */
-    product = count * to_len;
-    if (product / to_len != count) {
+    assert(count > 0);
+    if (to_len > (PY_SSIZE_T_MAX - self_len) / count) {
         PyErr_SetString(PyExc_OverflowError,
                         "replace string is too long");
         return NULL;
     }
-    result_len = product + self_len;
-    if (result_len < 0) {
-        PyErr_SetString(PyExc_OverflowError,
-                        "replace string is too long");
-        return NULL;
-    }
-
+    result_len = count * to_len + self_len;
     if (! (result = (PyStringObject *)
                      PyString_FromStringAndSize(NULL, result_len)) )
         return NULL;
@@ -2610,7 +2609,7 @@
     char *self_s, *result_s;
     char *start, *next, *end;
     Py_ssize_t self_len, result_len;
-    Py_ssize_t count, product;
+    Py_ssize_t count;
     PyStringObject *result;
 
     self_s = PyString_AS_STRING(self);
@@ -2624,16 +2623,12 @@
 
     /* use the difference between current and new, hence the "-1" */
     /*   result_len = self_len + count * (to_len-1)  */
-    product = count * (to_len-1);
-    if (product / (to_len-1) != count) {
+    assert(count > 0);
+    if (to_len - 1 > (PY_SSIZE_T_MAX - self_len) / count) {
         PyErr_SetString(PyExc_OverflowError, "replace string is too long");
         return NULL;
     }
-    result_len = self_len + product;
-    if (result_len < 0) {
-        PyErr_SetString(PyExc_OverflowError, "replace string is too long");
-        return NULL;
-    }
+    result_len = self_len + count * (to_len - 1);
 
     if ( (result = (PyStringObject *)
           PyString_FromStringAndSize(NULL, result_len)) == NULL)
@@ -2676,7 +2671,7 @@
     char *self_s, *result_s;
     char *start, *next, *end;
     Py_ssize_t self_len, result_len;
-    Py_ssize_t count, offset, product;
+    Py_ssize_t count, offset;
     PyStringObject *result;
 
     self_s = PyString_AS_STRING(self);
@@ -2693,16 +2688,12 @@
 
     /* Check for overflow */
     /*    result_len = self_len + count * (to_len-from_len) */
-    product = count * (to_len-from_len);
-    if (product / (to_len-from_len) != count) {
+    assert(count > 0);
+    if (to_len - from_len > (PY_SSIZE_T_MAX - self_len) / count) {
         PyErr_SetString(PyExc_OverflowError, "replace string is too long");
         return NULL;
     }
-    result_len = self_len + product;
-    if (result_len < 0) {
-        PyErr_SetString(PyExc_OverflowError, "replace string is too long");
-        return NULL;
-    }
+    result_len = self_len + count * (to_len - from_len);
 
     if ( (result = (PyStringObject *)
           PyString_FromStringAndSize(NULL, result_len)) == NULL)
diff --git a/Objects/unicodeobject.c b/Objects/unicodeobject.c
index ca609a9..7986d70 100644
--- a/Objects/unicodeobject.c
+++ b/Objects/unicodeobject.c
@@ -5732,20 +5732,20 @@
 
         /* Make sure we have enough space for the separator and the item. */
         itemlen = PyUnicode_GET_SIZE(item);
-        new_res_used = res_used + itemlen;
-        if (new_res_used < 0)
+        if (res_used > PY_SSIZE_T_MAX - itemlen)
             goto Overflow;
+        new_res_used = res_used + itemlen;
         if (i < seqlen - 1) {
-            new_res_used += seplen;
-            if (new_res_used < 0)
+            if (new_res_used > PY_SSIZE_T_MAX - seplen)
                 goto Overflow;
+            new_res_used += seplen;
         }
         if (new_res_used > res_alloc) {
             /* double allocated size until it's big enough */
             do {
-                res_alloc += res_alloc;
-                if (res_alloc <= 0)
+                if (res_alloc > PY_SSIZE_T_MAX / 2)
                     goto Overflow;
+                res_alloc += res_alloc;
             } while (new_res_used > res_alloc);
             if (_PyUnicode_Resize(&res, res_alloc) < 0) {
                 Py_DECREF(item);
@@ -5943,7 +5943,7 @@
     } else {
 
         Py_ssize_t n, i, j;
-        Py_ssize_t product, new_size, delta;
+        Py_ssize_t new_size, delta;
         Py_UNICODE *p;
 
         /* replace strings */
@@ -5956,18 +5956,13 @@
         if (delta == 0) {
             new_size = self->length;
         } else {
-            product = n * (str2->length - str1->length);
-            if ((product / (str2->length - str1->length)) != n) {
+            assert(n > 0);
+            if (delta > (PY_SSIZE_T_MAX - self->length) / n) {
                 PyErr_SetString(PyExc_OverflowError,
                                 "replace string is too long");
                 return NULL;
             }
-            new_size = self->length + product;
-            if (new_size < 0) {
-                PyErr_SetString(PyExc_OverflowError,
-                                "replace string is too long");
-                return NULL;
-            }
+            new_size = self->length + delta * n;
         }
         u = _PyUnicode_New(new_size);
         if (!u)