MPAL - Editorial

PROBLEM LINK:

Practice

Contest Code Battle 2021.1.2

Author: Rahul Sharma

Tester: Naman Mittal, Akshit Monga

Editorialist: Deepanshu Jindal

DIFFICULTY:

Easy

PREREQUISITES:

Basic observations, Frequency arrays/maps

PROBLEM:

Given a string of length N of lowercase alphabet and a pivot index P character can be inserted deleted cost 1 each or rearranged cost 0 on sub-string left of P^{th} character i.e. 1 to (P-1). Find minimum cost to make final string palindrome about P^{th} character if odd or P^{th} and (P+1)^{th} character if even.

QUICK EXPLANATION:

Maintain a map or frequency array of 26 as we have lower case alphabets only and keep track of the elements occurring on the left and the right of pivot. Find the number of deletions and insertions required considering both even and odd length case and print the minimum result.

EXPLANATION:

  1. We maintain a frequency array of size 26 named characterFrequency to store the difference in number of occurrences of each character in the left of pivot and in the right.
    We maintain this array such that for any character(ch) characterFrequency[ch]<0, represents deletion and characterFrequency[ch]>0 represents insertion of a character in the sub-string present on the left of Pivot.
    Hence,
    a) for occurrence of a character from index 1 to (P-1), we will subtract 1.
    b) and for occurrence of a character from index (P+1) to length of string N, we will add 1.

  2. Iterate over characterFrequency leaving the index of pivot character in original string and store in variable ops as absolute sum i.e. \sum_{i=1}^{26} charaterFrequency[i]. This is minimum operations if we make an odd length palindrome. Mark it as ans.

  3. Now there can be a case when P^{th} character is centre along with (P+1)^{th} character (e.g. a palindromic array of even size. In that case, we will have 2 centres).
    It is only possible if P^{th} and (P+1)^{th} characters are the same. Let frequency of pivot character be pivotFreq then operations required for making even length palindrome is ops = ops + abs(pivotFreq-1) - abs(pivotFreq).

  4. Final answer is minimum of previous answer in step 2 (ans) and new operations in step 3 (ops) i.e ans = min(ans, ops).

COMPLEXITIES:

Time Complexity: O(N+A) per test case where A=26 number of characters.
Auxillary Space Complexity: O(1) per test case since only frequency array of size 26 is used.

SOLUTIONS:

Language: C++, Python

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

//This function returns the minimum operation required to make the string palindromic
int minimumOperations(string str, int pivot)
{	
    int n = str.length();
    int ans = 0, pivotFreq = 0, ops = 0;
    int characterFrequency[26] = {0};// array that stores difference of occurence of character
    for(int i = 0; i < pivot-1; i++)
	   characterFrequency[str[i] - 'a']--;
    for(int i = pivot; i < n; i++)
	   characterFrequency[str[i] - 'a']++;

    // Pth centre
    for(int i = 0; i < 26; i++)
	   ops = ops + abs(characterFrequency[i]);
    ans = ops;

    // Pth and (P+1)th centre
    pivotFreq = characterFrequency[str[pivot-1] - 'a'];
    if(pivot < n && str[pivot-1] == str[pivot])
       ans = min(ans, ops + abs(pivotFreq - 1) - abs(pivotFreq));

   return ans;
} 
int main()
{
    string str;
    int pivot, t;
    cin >> t;
    while(t--)
    {
	    cin >> str >> pivot;
	    cout << minimumOperations(str, pivot) << '\n';
    }

    return 0;
}
Tester's Solution
'''Author- Akshit Monga'''
from sys import stdin, stdout
# input = stdin.readline
t = int(input())
for _ in range(t):
    s,p=input().split()
    p=int(p)-1
    n=len(s)
    vals=[0 for i in range(26)]
    for i in range(n):
        if i<p:
            vals[ord(s[i])-97]+=1
        elif i>p:
            vals[ord(s[i])-97]-=1
    ans1=0
    ans2=0
    for i in vals:
        ans1+=abs(i)
        ans2+=abs(i)
    if p==n-1 or s[p]!=s[p+1]:
        print(ans1)
        continue
    print(min(ans1,ans1-abs(vals[ord(s[p+1])-97])+abs(vals[ord(s[p+1])-97]+1))) 
1 Like