Data Modelling & AI Data Structure & Algorithm

Maximum number of given operations to remove the entire string

21 June 2025

0

Given string str containing lowercase English characters, we can perform the following two operations on the given string:

Remove the entire string.
Remove a prefix of the string str[0…i] only if it is equal to the sub-string str[(i + 1)…(2 * i + 1)].

The task is to find the maximum number of operations required to delete the entire string.

Examples:

Input: str = “abababab”
Output: 4
Explanation:
Operation 1: Delete prefix “ab” and the string becomes “ababab”.
Operation 2: Delete prefix “ab” and the string becomes “abab”.
Operation 3: Delete prefix “ab”, str = “ab”.
Operation 4: Delete the entire string.

Input: s = “abc”
Output: 1

Approach using KMP + Dynamic programming:

The idea is to store all possible length deletion of 2nd operation for every index of the given string and explore every possible deletion on each index and return the maximum operation among them.

Follow the step below to implement the above idea:

Iterate over all the indexes and find What are the possible deletions using 2nd operation that can be performed starting at index i.
- Use KMP algorithm to find all such possible deletions.
  - If LPS (longest common prefix which is also a suffix) ending at i satisfy the condition that the length of substring ending at i is double the length of LPS at i, then this is a possible jump and store it into some array.
Iterate over each index and go for every possible length of deletion at index i and maximize the result.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// For storing all possible length deletion at index i
vector<vector<int> > arr;
 
// For memoization
vector<int> dp;
 
// Use modified KMP to find valid deletion
vector<int> KMP(string& s)
{
    int n = s.size();
    vector<int> pi(n);
 
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
 
        if (s[i] == s[j]) {
            pi[i] = j + 1;
        }
        else {
            while (j > 0 && s[i] != s[j]) {
                j = pi[j - 1];
            }
 
            if (s[i] == s[j]) {
                pi[i] = j + 1;
            }
            else {
                pi[i] = 0;
            }
        }
    }
 
    // Store all possible length deletion
    // which follow the given condition that
    // Remove a prefix of the string str[0…i]
    // only if it is equal to the sub-string
    // str[(i + 1)…(2 * i + 1)].
    vector<int> res;
 
    for (int i = 0; i < n; i++) {
        if (i + 1 - pi[i] == pi[i]) {
            res.push_back(pi[i]);
        }
    }
 
    return res;
}
 
// Function to find all maximum possible deletion
int solve(int i, int n)
{
    if (i >= n)
        return 0;
    if (arr[i].size() == 0)
        return 1;
 
    if (dp[i] != -1)
        return dp[i];
 
    int res = 0;
 
    // Iterate over each index and go for ever possible
    // length of deletion at index i
    for (int jump : arr[i]) {
        res = max(res, 1 + solve(i + jump, n));
    }
 
    // Store the maximum possible deletion
    // at index i into res and return the res.
    return dp[i] = res;
}
 
int deleteString(string s)
{
    int n = s.size();
    dp.resize(n + 1, -1);
 
    // Iterate over all the index and find
    // What are the possible deletion that can be
    // Perform starting from index i
    for (int i = 0; i < n; i++) {
        string sub = s.substr(i);
        arr.push_back(KMP(sub));
    }
 
    // Function call for finding the maximum deletion
    // operation required
    return solve(0, n);
}
 
// Driver code
int main()
{
    // Input string
    string s = "abababab";
 
    // Function call
    cout << deleteString(s);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
import java.util.*;
 
class GFG {
    // Use modified KMP to find valid deletion
    public static List<Integer> KMP(StringBuilder s)
    {
        int n = s.length();
        Integer[] temp = new Integer[n];
        Arrays.fill(temp, 0);
        List<Integer> pi = Arrays.asList(temp);
 
        for (int i = 1; i < n; i++) {
            int j = pi.get(i - 1);
 
            if (s.charAt(i) == s.charAt(j)) {
                pi.set(i, j + 1);
            }
            else {
                while (j > 0
                       && s.charAt(i) != s.charAt(j)) {
                    j = pi.get(j - 1);
                }
 
                if (s.charAt(i) == s.charAt(j)) {
                    pi.set(i, j + 1);
                }
                else {
                    pi.set(i, 0);
                }
            }
        }
 
        // Store all possible length deletion
        // which follow the given condition that
        // Remove a prefix of the string str[0…i]
        // only if it is equal to the sub-string
        // str[(i + 1)…(2 * i + 1)].
        List<Integer> res = new ArrayList<Integer>();
 
        for (int i = 0; i < n; i++) {
            if (i + 1 - pi.get(i) == pi.get(i)) {
                res.add(pi.get(i));
            }
        }
 
        return res;
    }
 
    // Function to find all maximum possible deletion
    public static int solve(int i, int n, int[] dp,
                            List<List<Integer> > arr)
    {
        if (i >= n)
            return 0;
        if (arr.get(i).size() == 0)
            return 1;
 
        if (dp[i] != -1)
            return dp[i];
 
        int res = 0;
 
        // Iterate over each index and go for ever possible
        // length of deletion at index i
        for (int jump : arr.get(i)) {
            res = Math.max(res,
                           1 + solve(i + jump, n, dp, arr));
        }
 
        // Store the maximum possible deletion
        // at index i into res and return the res.
        return dp[i] = res;
    }
 
    public static int deleteString(StringBuilder s,
                                   List<List<Integer> > arr)
    {
        int n = s.length();
 
        int[] dp = new int[n + 1];
 
        // For memoization
        Arrays.fill(dp, -1);
 
        // Iterate over all the index and find
        // What are the possible deletion that can be
        // Perform starting from index i
        for (int i = 0; i < n; i++) {
            StringBuilder sub
                = new StringBuilder(s.substring(i));
            arr.add(KMP(sub));
        }
 
        // Function call for finding the maximum deletion
        // operation required
        return solve(0, n, dp, arr);
    }
 
    public static void main(String[] args)
    {
        StringBuilder s = new StringBuilder("abababab");
 
        // For storing all possible length deletion at index
        // i
        List<List<Integer> > arr
            = new ArrayList<List<Integer> >();
 
        // Function call
        System.out.println(deleteString(s, arr));
    }
}

Python3

# Python implementation of the approach
 
# For storing all possible length deletion at index i
arr=[];
 
# For memoization
dp=[];
 
# Use modified KMP to find valid deletion
def KMP( s):
    n = len(s);
    pi=[0]*n;
 
    for i in range(1,n):
        j = pi[i - 1];
 
        if (s[i] == s[j]) :
            pi[i] = j + 1;
         
        else :
            while (j > 0 and s[i] != s[j]) :
                j = pi[j - 1];
             
 
            if (s[i] == s[j]): 
                pi[i] = j + 1;
             
            else :
                pi[i] = 0;
             
         
     
 
    # Store all possible length deletion
    # which follow the given condition that
    # Remove a prefix of the string str[0…i]
    # only if it is equal to the sub-string
    # str[(i + 1)…(2 * i + 1)].
    res=[];
 
    for i in range(0,n):
        if (i + 1 - pi[i] == pi[i]) :
            res.append(pi[i]);
             
    return res;
 
 
# Function to find all maximum possible deletion
def solve( i,  n):
 
    if (i >= n):
        return 0;
    if (len(arr[i]) == 0):
        return 1;
 
    if (dp[i] != -1):
        return dp[i];
 
    res = 0;
 
    # Iterate over each index and go for ever possible
    # length of deletion at index i
    for jump in arr[i]:
        res = max(res, 1 + solve(i + jump, n));
     
 
    # Store the maximum possible deletion
    # at index i into res and return the res.
    dp[i]=res;
    return dp[i];
 
 
def deleteString( s):
    n = len(s);
    for i in range(0,n+1):
        dp.append(-1);
 
    # Iterate over all the index and find
    # What are the possible deletion that can be
    # Perform starting from index i
    for i in range(0,n):
        sub = s[i:n];
        arr.append(KMP(sub));
     
 
    # Function call for finding the maximum deletion
    # operation required
    return solve(0, n);
 
 
# Driver code
# Input string
s = "abababab";
 
# Function call
print(deleteString(s));
 
# this code is contributed by poojaagarwal2.

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG {
    // Use modified KMP to find valid deletion
    public static List<int> KMP(string s)
    {
        int n = s.Length;
        int[] temp = new int[n];
        for (int i = 0; i < n; i++) {
            temp[i] = 0;
        }
        List<int> pi = new List<int>(temp);
 
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
 
            if (s[i] == s[j]) {
                pi[i] = j + 1;
            }
            else {
                while (j > 0 && s[i] != s[j]) {
                    j = pi[j - 1];
                }
 
                if (s[i] == s[j]) {
                    pi[i] = j + 1;
                }
                else {
                    pi[i] = 0;
                }
            }
        }
 
        // Store all possible length deletion
        // which follow the given condition that
        // Remove a prefix of the string str[0…i]
        // only if it is equal to the sub-string
        // str[(i + 1)…(2 * i + 1)].
        List<int> res = new List<int>();
 
        for (int i = 0; i < n; i++) {
            if (i + 1 - pi[i] == pi[i]) {
                res.Add(pi[i]);
            }
        }
 
        return res;
    }
 
    // Function to find all maximum possible deletion
    public static int solve(int i, int n, int[] dp,
                            List<List<int> > arr)
    {
        if (i >= n)
            return 0;
        if (arr[i].Count == 0)
            return 1;
 
        if (dp[i] != -1)
            return dp[i];
 
        int res = 0;
 
        // Iterate over each index and go for ever possible
        // length of deletion at index i
        foreach (int jump in arr[i]) {
            res = Math.Max(res,
                           1 + solve(i + jump, n, dp, arr));
        }
 
        // Store the maximum possible deletion
        // at index i into res and return the res.
        return dp[i] = res;
    }
 
    public static int deleteString(string s,
                                   List<List<int> > arr)
    {
        int n = s.Length;
 
        int[] dp = new int[n + 1];
 
        // For memoization
        for (int i = 0; i < n + 1; i++) {
            dp[i] = -1;
        }
 
        // Iterate over all the index and find
        // What are the possible deletion that can be
        // Perform starting from index i
        for (int i = 0; i < n; i++) {
            string sub
                = s.Substring(i);
            arr.Add(KMP(sub));
        }
        // Function call for finding the maximum deletion
        // operation required
        return solve(0, n, dp, arr);
    }
 
    public static void Main(string[] args)
    {
        string s ="abababab";
 
        // For storing all possible length deletion at index
        // i
        var arr = new List<List<int> >();
 
        // Function call
        Console.WriteLine(deleteString(s, arr));
    }
}
//This code is contributed by ik_9

Javascript

// JavaScript implementation of the approach
 
// Use modified KMP to find valid deletion
function KMP(s) {
let n = s.length;
let pi = new Array(n);
 
for (let i = 1; i < n; i++) {
let j = pi[i - 1];
if (s[i] === s[j]) {
  pi[i] = j + 1;
} else {
  while (j > 0 && s[i] !== s[j]) {
j = pi[j - 1];
  }
 
  if (s[i] === s[j]) {
pi[i] = j + 1;
  } else {
pi[i] = 0;
  }
}
}
 
// Store all possible length deletion
// which follow the given condition that
// Remove a prefix of the string str[0…i]
// only if it is equal to the sub-string
// str[(i + 1)…(2 * i + 1)].
let res = [];
 
for (let i = 0; i < n; i++) {
if (i + 1 - pi[i] === pi[i]) {
res.push(pi[i]);
}
}
 
return res;
}
 
// Function to find all maximum possible deletion
function solve(i, n, arr, dp) {
if (i >= n) return 0;
if (arr[i].length === 0) return 1;
 
if (dp[i] !== -1) return dp[i];
 
let res = 0;
 
// Iterate over each index and go for ever possible
// length of deletion at index i
for (let jump of arr[i]) {
res = Math.max(res, 1 + solve(i + jump, n, arr, dp));
}
// Store the maximum possible deletion
// at index i into res and return the res.
return (dp[i] = res);
}
 
function deleteString(s) {
let n = s.length;
let dp = Array(n + 1).fill(-1);
let arr = [];
 
// Iterate over all the index and find
// What are the possible deletion that can be
// Perform starting from index i
for (let i = 0; i < n; i++) {
let sub = s.substring(i);
arr.push(KMP(sub));
}
 
// Function call for finding the maximum deletion
// operation required
return solve(0, n, arr, dp);
}
 
// Driver code
 
// Input string
let s = "abababab";
 
// Function call
console.log(deleteString(s));
 
// This code is contributed by Aman Kumar.

Output

Time Complexity: O(N²)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Maximum number of given operations to remove the entire string

Approach using KMP + Dynamic programming:

C++

Java

Python3

C#

Javascript

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

Beyond Context Overload: How Parlant × Milvus Brings Control and Clarity to LLM Agent Behavior

Understanding IVF Vector Index: How It Works and When to Choose It Over HNSW

LEAVE A REPLY Cancel reply

Most Popular

How to Jailbreak a FireStick in 2025: Step-by-Step Guide by Tim Mocan

How to Set Up a VPN on Any Device in 2025 (Full Guide) by Tim Mocan

How to Change Your IP Address on Mac: Full 2025 Guide by Ana Jovanovic

How to Install a VPN on Fire TV Stick: Complete 2025 Guide by Todd Faulk

EDITOR PICKS

How to Jailbreak a FireStick in 2025: Step-by-Step Guide by Tim Mocan

How to Set Up a VPN on Any Device in 2025 (Full Guide) by Tim Mocan

How to Change Your IP Address on Mac: Full 2025 Guide by Ana Jovanovic

POPULAR POSTS

How to Jailbreak a FireStick in 2025: Step-by-Step Guide by Tim Mocan

How to Set Up a VPN on Any Device in 2025 (Full Guide) by Tim Mocan

How to Change Your IP Address on Mac: Full 2025 Guide by Ana Jovanovic

POPULAR CATEGORY

ABOUT US

FOLLOW US