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.
- Use KMP algorithm to find all such possible deletions.
- 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 ivector<vector<int> > arr;// For memoizationvector<int> dp;// Use modified KMP to find valid deletionvector<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 deletionint 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 codeint main(){ // Input string string s = "abababab"; // Function call cout << deleteString(s); return 0;} |
Java
// Java implementation of the approachimport 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 iarr=[];# For memoizationdp=[];# Use modified KMP to find valid deletiondef 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 deletiondef 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 strings = "abababab";# Function callprint(deleteString(s));# this code is contributed by poojaagarwal2. |
C#
// C# implementation of the approachusing 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 deletionfunction 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 deletionfunction 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 ifor (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 ifor (let i = 0; i < n; i++) {let sub = s.substring(i);arr.push(KMP(sub));}// Function call for finding the maximum deletion// operation requiredreturn solve(0, n, arr, dp);}// Driver code// Input stringlet s = "abababab";// Function callconsole.log(deleteString(s));// This code is contributed by Aman Kumar. |
Output
4
Time Complexity: O(N2)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
