diff --git a/Objects/stringlib/transmogrify.h b/Objects/stringlib/transmogrify.h
index 9506019..e1165ea 100644
--- a/Objects/stringlib/transmogrify.h
+++ b/Objects/stringlib/transmogrify.h
@@ -680,9 +680,13 @@
                   const char *to_s, Py_ssize_t to_len,
                   Py_ssize_t maxcount)
 {
+    if (STRINGLIB_LEN(self) < from_len) {
+        /* nothing to do; return the original bytes */
+        return return_self(self);
+    }
     if (maxcount < 0) {
         maxcount = PY_SSIZE_T_MAX;
-    } else if (maxcount == 0 || STRINGLIB_LEN(self) == 0) {
+    } else if (maxcount == 0) {
         /* nothing to do; return the original bytes */
         return return_self(self);
     }
@@ -699,13 +703,6 @@
         return stringlib_replace_interleave(self, to_s, to_len, maxcount);
     }
 
-    /* Except for b"".replace(b"", b"A") == b"A" there is no way beyond this */
-    /* point for an empty self bytes to generate a non-empty bytes */
-    /* Special case so the remaining code always gets a non-empty bytes */
-    if (STRINGLIB_LEN(self) == 0) {
-        return return_self(self);
-    }
-
     if (to_len == 0) {
         /* delete all occurrences of 'from' bytes */
         if (from_len == 1) {
diff --git a/Objects/unicodeobject.c b/Objects/unicodeobject.c
index 2d60627..5ae0af8 100644
--- a/Objects/unicodeobject.c
+++ b/Objects/unicodeobject.c
@@ -10572,9 +10572,12 @@
     int mayshrink;
     Py_UCS4 maxchar, maxchar_str1, maxchar_str2;
 
+    if (slen < len1)
+        goto nothing;
+
     if (maxcount < 0)
         maxcount = PY_SSIZE_T_MAX;
-    else if (maxcount == 0 || slen == 0)
+    else if (maxcount == 0)
         goto nothing;
 
     if (str1 == str2)