Given a string S of length N. Select a Subsequence of character, delete it, and concatenate the remaining part of the String S. Let’s say the remaining part will be S1. Then the task is to output the minimum possible sum of actual indices of S1 with respect to S and S1 must have a length greater than 1, which becomes a palindrome. If not possible to make S1 palindrome then output -1.
Examples:
Input: N = 5, S = “baabx”
Output: 5
Explanation: Delete the sub-sequence aax (baabx), So that the remaining String will be bb, Which is a palindrome. The sum of actual indices of characters in “bb” is 1 + 4 = 5. Because b and b characters are placed at the 1st and 4th index of S or we can say the actual value of indices in a concatenated string with respect to S. It should be noted that, If we delete the sub-sequence bbx(baabx) then the remaining String becomes “aa”, having actual indices sum as 2 + 3 = 5. It is also a possible answer.Input: N = 3, S = “abc”
Output: -1
Explanation: It can be verified that deleting any possible sub-sequence can’t make any palindromic string, So no minimum possible sum exists.
Approach: Implement the idea below to solve the problem
The problem is Greedy logic based and can be solved by using the HashMap data structure. For more clarification see the Concept of approach section.
Concept of approach:
It is clear that we have to make a palindrome String of length greater than 1, So the length which is just greater than 1 is 2.
We are taking the length 2 because it is just greater than 1 and it is a length such that it can form a palindrome string. Except it we have to minimize the number of characters in S1, so that the sum of actual indices will be the minimum possible. Thus, 2 is an optimal length for S1.
So, the observation comes that we have to delete sub-sequence in such a way that palindrome string S1 must have only 2 characters and for making S1 palindrome, That 2 characters must be the same.
For example: S = “bacb”
Deleted sub-sequence = ac (bacb)
S1 after deleting sub-sequence = bbPlease note that we can also make S1 = bab, Which is also a palindrome, from the above case. But due to the increase in number of characters, the sum of actual indices will only increase more. Therefore, we will not take length 3 for making S1 palindrome. For minimizing sum the actual indices value of those two same characters must be nearest to first index.
For example: S = “baba”
There can be two cases either delete sub-sequence aa(baba) or bb(baba), which gives S1 as “bb” or “aa” respectively. “bb” has sum of actual indices as = 1 + 3 = 4 and “aa” has 2 + 4 = 6 . As 4 < 6, Therefore, minimum possible value is 4 for this case. It should be noted that characters b, b is nearer to first index than a, a in S.
Final observation is:
- Find two same characters in S, such that they are same and nearest to first index, Formally two same characters at leftmost side. Examples:
- abbaccs
- xabcxz
Steps were taken to solve the problem:
- Create a boolean flag and initialize it as false.
- Create variable minSum.
- Create a HashMap, let’s say map.
- Run a loop for i = 0 to i < N and follow the below-mentioned steps under the scope of the loop:
- If ( map.containsKey( s.charAt( i ) ) == false)
- map.put(s.charAt( i ), (i + 1))
- Else
- minSum = (i + 1) + map.get(s.charAt( i ))
- flag = true and then break the loop.
- If ( map.containsKey( s.charAt( i ) ) == false)
- If the flag value is true, then output the value of minSum, else output -1.
Below is the code to implement the approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Method for finding minimum possible// sum of indicesvoid minimumSum(string s, int n){ // boolean Flag initialized to false bool flag = false; // Variable for holding minimum // possible sum of actual indices int minSum = 0; // Map for storing // <Character, IndexNumber> pair unordered_map<char, int> mp; // Loop for traversing over S for (int i = 0; i < n; i++) { // If current character not // exist in Map Then putting // that character along with // its 1 based indexing if (mp.find(s[i]) == mp.end()) { mp[s[i]] = i + 1; } // If current character is // already stored in map then // initializing minSum as sum of // index of current character // and the index stored // previously of the same character else { minSum = (i + 1) + mp[s[i]]; // Marking flag as true, So // that we can know Palindrome // forming is possible or not flag = true; break; } } // Printing output on // the basis of flag if (flag) cout << minSum << endl; else cout << "-1" << endl;}int main(){ int n = 7; string s = "bxyzabb"; // Function call minimumSum(s, n);} |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Driver Function public static void main(String[] args) throws java.lang.Exception { int n = 7; String s = "bxyzabb"; // Function call minimumSum(s, n); } // Method for finding minimum possible // sum of indices static void minimumSum(String s, int n) { // boolean Flag initialized to false boolean flag = false; // Variable for holding minimum // possible sum of actual indices int minSum = 0; // HashMap for storing // <Character, IndexNumber> pair HashMap<Character, Integer> map = new HashMap<>(); // Loop for traversing over S for (int i = 0; i < n; i++) { // If current character not // exist in Map Then putting // that character along with // its 1 based indexing if (!map.containsKey(s.charAt(i))) { map.put(s.charAt(i), (i + 1)); } // If current character is // already stored in map then // initializing minSum as sum of // index of current character // and the index stored // previously of the same character else { minSum = (i + 1) + map.get(s.charAt(i)); // Marking flag as true, So // that we can know Palindrome // forming is possible or not flag = true; break; } } // Printing output on // the basis of flag System.out.println(flag == true ? minSum : -1); }} |
Python3
# Python code to implement the approach# Method for finding minimum possible# sum of indicesdef minimumSum(s, n): # boolean Flag initialized to false flag = False # Variable for holding minimum # possible sum of actual indices minSum = 0 # Dictionary for storing # <Character, IndexNumber> pair map = {} # Loop for traversing over S for i in range(n): # If current character not # exist in Map Then putting # that character along with # its 1 based indexing if s[i] not in map: map[s[i]] = i + 1 # If current character is # already stored in map then # initializing minSum as sum of # index of current character # and the index stored # previously of the same character else: minSum = i + 1 + map[s[i]] # Marking flag as true, So # that we can know Palindrome # forming is possible or not flag = True break # Printing output on # the basis of flag print(minSum if flag else -1)# Driver Functionif __name__ == "__main__": n = 7 s = "bxyzabb" # Function call minimumSum(s, n)# This code is contributed by sankar. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { // Method for finding minimum possible // sum of indices static void minimumSum(string s, int n) { // boolean Flag initialized to false bool flag = false; // Variable for holding minimum // possible sum of actual indices int minSum = 0; // Map for storing // <Character, IndexNumber> pair Dictionary<char, int> mp = new Dictionary<char, int>(); // Loop for traversing over S for (int i = 0; i < n; i++) { // If current character not // exist in Map Then putting // that character along with // its 1 based indexing if (!mp.ContainsKey(s[i])) { mp[s[i]] = i + 1; } // If current character is // already stored in map then // initializing minSum as sum of // index of current character // and the index stored // previously of the same character else { minSum = (i + 1) + mp[s[i]]; // Marking flag as true, So // that we can know Palindrome // forming is possible or not flag = true; break; } } // Printing output on // the basis of flag if (flag) Console.WriteLine(minSum); else Console.WriteLine("-1"); } static public void Main(string[] args) { int n = 7; string s = "bxyzabb"; // Function call minimumSum(s, n); }}// This code is contributed by prasad264 |
Javascript
// Javascript code to implement the approach// Function for finding minimum possible// sum of indicesfunction minimumSum(s, n) { // boolean Flag initialized to false let flag = false; // Variable for holding minimum // possible sum of actual indices let minSum = 0; // Map for storing // <Character, IndexNumber> pair let map = new Map(); // Loop for traversing over S for (let i = 0; i < n; i++) { // If current character not // exist in Map Then putting // that character along with // its 1 based indexing if (!map.has(s.charAt(i))) { map.set(s.charAt(i), (i + 1)); } // If current character is // already stored in map then // initializing minSum as sum of // index of current character // and the index stored // previously of the same character else { minSum = (i + 1) + map.get(s.charAt(i)); // Marking flag as true, So // that we can know Palindrome // forming is possible or not flag = true; break; } } // Printing output on // the basis of flag console.log(flag ? minSum : -1);}let s = "bxyzabb";let n = 7;// Function callminimumSum(s, n);// This code is contributed by Susobhan Akhuli |
7
Time Complexity: O(N), As String is traversed
Auxiliary Space: O(N), As HashMap is used
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
