Use the KMP algorithm to find all occurrences of the pattern in the text, which takes O(n) time.

Store these positions in an array (let's call it positionArray).

Utilize a StringBuilder to construct the final string with replacements.

Maintain a pointer (positionPointer) to track the index in positionArray.

Traverse the text from left to right.

Append characters to the StringBuilder, except at positions indicated by positionPointer; here, append the replacement string instead and skip the pattern length in the text.

Adjust positionPointer appropriately to manage overlapping patterns (e.g., in a text like "aaaaaa" with pattern "aa" replaced by "X").

Pseudocode

positions = KMP_SEARCH(text, pattern)
StringBuilder result
positionPointer = 0
for each character in text:
    if positionPointer < length of positions and current index is positions[positionPointer]:
        append replacement to result
        skip pattern length in text
        positionPointer++
    else:
        append current character to result

Code

[{"language":"Java","code":"public class Solution {\n    public String replace(final String text, final String pattern, final String replaceWith) throws Exception {\n        if (text.equals(pattern)) {\n            return replaceWith;\n        }\n        if (pattern == null || pattern.isEmpty() || replaceWith == null || replaceWith.isEmpty()) {\n            return text;\n        }\n\n        List<Integer> positions = KMPSearch(text, pattern);\n        StringBuilder replacedString = new StringBuilder();\n        int positionPointer = 0;\n        int i = 0;\n\n        while (i < text.length()) {\n            if (positionPointer < positions.size() && i == positions.get(positionPointer)) {\n                replacedString.append(replaceWith);\n                i += pattern.length();\n                positionPointer++;\n            } else {\n                replacedString.append(text.charAt(i));\n                i++;\n            }\n        }\n\n        return replacedString.toString();\n    }\n\n    private List<Integer> KMPSearch(String text, String pattern) {\n        int[] lps = computeLPSArray(pattern);\n        List<Integer> positions = new ArrayList<>();\n        int i = 0;\n        int j = 0;\n\n        while (i < text.length()) {\n            if (pattern.charAt(j) == text.charAt(i)) {\n                i++;\n                j++;\n            }\n            if (j == pattern.length()) {\n                positions.add(i - j);\n                j = lps[j - 1];\n            } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {\n                if (j != 0) {\n                    j = lps[j - 1];\n                } else {\n                    i++;\n                }\n            }\n        }\n        return positions;\n    }\n\n    private int[] computeLPSArray(String pattern) {\n        int length = 0;\n        int i = 1;\n        int[] lps = new int[pattern.length()];\n        lps[0] = 0;\n\n        while (i < pattern.length()) {\n            if (pattern.charAt(i) == pattern.charAt(length)) {\n                length++;\n                lps[i] = length;\n                i++;\n            } else {\n                if (length != 0) {\n                    length = lps[length - 1];\n                } else {\n                    lps[i] = 0;\n                    i++;\n                }\n            }\n        }\n        return lps;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def replace(self, text: str, pattern: str, replace_with: str) -> str:\n        if text == pattern:\n            return replace_with\n        if not pattern or not replace_with:\n            return text\n\n        positions = self.kmp_search(text,

Related Tags