Given a character array, str[] consisting of N lowercase alphabets, and an integer array, arr[] consisting of numbers in the range [0, N – 1]. Following are the operations that will be performed in the problem:
- Traverse the character array str[] from left to right.
- For every ith index, store the smallest odd length(>1) intervals (if exists), say [L, R] such that str[L] = str[R].
The task is to find the lexicographically smallest character from str[] that satisfies exactly one of the following conditions:
- No odd length intervals exist for the character where str[L] == str[R].
- All intervals of the character must contain different indexed array element.
Examples:
Input: str[] = { ‘a’, ‘b’, ‘c’, ‘a’, ‘e’, ‘a’, ‘a’ }, arr[] = { 4, 6 }
Output: a
Explanation:
Possible smallest odd-length interval of the character ‘a’ in str are { [0, 6], [3, 5] }
Since the interval [0, 6] contains arr[1] and the interval [3, 5] contains arr[0]. Therefore, the required output is ‘a’.Input: str[] = { ‘a’, ‘b’, ‘c’, ‘d’ }, arr[] = { 3, 4 }
Output: a
Explanation:
Since no interval exist for any element of the character array. Therefore, the lexicographically smallest character of str[] is ‘a’.Input: str[] = { ‘z’, ‘z’, ‘z’, ‘z’ }, arr[] = { 2 }
Output: -1
Explanation:
Possible smallest odd-length intervals of the character ‘z’ are { [0, 2], [1, 3] }
Since the interval [0, 2] contain arr[0] and the interval [1, 3] also contain arr[0] which is not distinct indexed array element. Therefore, the required output is -1.
Approach: The idea is to find the smallest odd-length intervals for every possible indices of str[]. Traverse each distinct character of str[] and check if the character satisfies the above conditions or not. If more than one characters satisfy the above conditions then print the lexicographically smallest character from them. Follow the steps below to solve the problem:
- Initialize an array, say hash[], to check if a character present in the character array, str[] or not.
- Initialize an ArrayList, say intervals[], of the form { X, Y } to store the start and end point of the smallest odd-length intervals.
- Traverse the array hash[] and store all the smallest odd-length intervals of each distinct character of str[].
- Sort intervals[] on the increasing order of X.
- Sort the array arr[] in increasing order.
- Check all the intervals of a character satisfy the above conditions or not by performing the following operations:
- Initialize a PriorityQueue say, PQ to store the intervals on increasing order of Y of the intervals.
- Traverse the arr[] array from left to right using variable i. For every ith index of arr[], traverse the intervals[] using variable j and check if start point of intervals[j] is less than arr[i] or not. If found to be true then insert the interval into PQ.
- If arr[i] is present in a range of the interval, then remove the top element of PQ to ensure that the distinct indexed array elements are assigned to different intervals.
- If at any point of time arr[i] is less than the end point of intervals[i] or the end point of top element of PQ is less than arr[i] then print -1.
- Otherwise, print the lexicographically smallest character from the array arr[] that satisfies the conditions.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Structure of an intervalclass SpecialInterval {public: int low, high; SpecialInterval(int low, int high) { // Stores start point of // an interval this->low = low; // Stores end point of // an interval this->high = high; }};// Function to check if a character// present in arr[] or notbool checkChar(string str){ bool hash[26] = { false }; for (int i = 0; i < str.length(); i++) { hash[str[i] - 'a'] = true; } return *hash;}// Function to check if all the intervals of a// character satisfies the condition or notbool checkIfValid(vector<SpecialInterval> intervals, vector<int> arr){ // If no intervals found for // the current character if (intervals.size() == 0) { return true; } // Sort intervals on increasing // order of start point sort(intervals.begin(), intervals.end(), [](SpecialInterval a, SpecialInterval b) { return a.low < b.low; }); // Store the intervals on increasing // order of end point of interval priority_queue<int, vector<int>, greater<int> > pq; // Stores count of array elements that // is present in different intervals int count = 0, j = 0; for (int i = 0; i < arr.size() && count < intervals.size(); i++) { while (j < intervals.size()) { SpecialInterval interval = intervals[j]; if (interval.low > arr[i]) break; j++; pq.push(interval.high); } if (pq.size() > 0) { int high = pq.top(); pq.pop(); if (arr[i] > high) { break; } count++; } } return count == intervals.size();}// Function to find the intervals// for each distinct character of str[]vector<SpecialInterval> findSpecialIntevals(string str, char ch){ // Stores the odd index // of the character array int oddPrev = -1; // Stores even index of // the character array int evenPrev = -1; vector<SpecialInterval> intervals; for (int i = 0; i < str.length(); i++) { if (str[i] == ch) { if (i % 2 == 0) { if (evenPrev == -1) { evenPrev = i; } else { SpecialInterval interval(evenPrev, i); intervals.push_back(interval); evenPrev = -1; } } else { if (oddPrev == -1) { oddPrev = i; } else { SpecialInterval interval(oddPrev, i); intervals.push_back(interval); oddPrev = -1; } } } } return intervals;}// Function to print lexicographically smallest// character that satisfies the conditionvoid printAnswer(vector<char> str, vector<int> arr){ sort(arr.begin(), arr.end()); bool possible = false; // Traverse all possible distinct // character of str for (int ch = 0; ch < 26; ch++) { if (!checkChar(string(str.begin(), str.end()))) continue; vector<SpecialInterval> intervals = findSpecialIntevals( string(str.begin(), str.end()), ch + 'a'); possible = checkIfValid(intervals, arr); if (possible) { cout << char(ch + 'a') << endl; break; } } if (!possible) cout << -1 << endl;}// Driver Codeint main(){ vector<char> str = { 'a', 'b', 'c', 'a', 'e', 'a', 'a' }; vector<int> arr = { 4, 6 }; printAnswer(str, arr); return 0;} |
Java
// Java Program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Structure of an interval static class SpecialInterval { // Stores start point of // an interval int low = 0; // Stores end point of // an interval int high = 0; // Initialize a interval SpecialInterval(int low, int high) { this.low = low; this.high = high; } } // Function to check if a character // present in arr[] or not static boolean[] checkChar(char[] str) { // hash[i]: Check if character i // is present in arr[] or not boolean[] hash = new boolean[26]; // Traverse the character array for (int i = 0; i < str.length; i++) { // Mark arr[i] as true hash[str[i] - 'a'] = true; } return hash; } // Function to check if all the intervals of a // character satisfies the condition or not private static boolean checkIfValid(List<SpecialInterval> intervals, int[] arr) { // If no intervals found for // the current character if (intervals.size() == 0) { return true; } // Sort intervals on increasing // order of start point Collections.sort( intervals, (interval1, interval2) -> interval1.low - interval2.low); // Store the intervals on increasing // order of end point of interval PriorityQueue<SpecialInterval> pq = new PriorityQueue<SpecialInterval>( intervals.size(), (interval1, interval2) -> interval1.high - interval2.high); // Stores count of array elements that // is present in different intervals int count = 0; // Stores index of an interval int j = 0; // Traverse the character array for (int i = 0; i < arr.length && count < intervals.size(); i++) { // Traverse intervals[] array while (j < intervals.size()) { // Stores interval // at j-th index SpecialInterval interval = intervals.get(j); // If start point of interval // greater than arr[i] if (interval.low > arr[i]) break; // Update j j++; // Insert interval into pq pq.offer(interval); } // If count of intervals // in pq greater than 0 if (pq.size() > 0) { // Stores top element of pq SpecialInterval interval = pq.poll(); // arr[i] does not lie in // the range of the interval if (arr[i] > interval.high) { break; } // Update count count++; } } return count == intervals.size(); } // Function to find the intervals // for each distinct character of str[] private static List<SpecialInterval> findSpecialIntevals(char[] str, char ch) { // Stores the odd index // of the character array int oddPrev = -1; // Stores even index of // the character array int evenPrev = -1; // Stores all intervals for each // distinct character of str List<SpecialInterval> intervals = new ArrayList<SpecialInterval>(); // Traverse the character array for (int i = 0; i < str.length; i++) { if (str[i] == ch) { // If i is even if (i % 2 == 0) { // If evenPrev not // equal to -1 if (evenPrev == -1) { // Update evenPrev evenPrev = i; } else { // Initialize an interval SpecialInterval interval = new SpecialInterval(evenPrev, i); // Insert current interval // into intervals intervals.add(interval); // Update evenPrev evenPrev = -1; } } else { // If oddPrev not // equal to -1 if (oddPrev == -1) { // Update oddPrev oddPrev = i; } else { // Initialize an interval SpecialInterval interval = new SpecialInterval(oddPrev, i); // Insert current interval // into intervals intervals.add(interval); // Update oddPrev oddPrev = -1; } } } } return intervals; } // Function to print lexicographically smallest // character that satisfies the condition static void printAnswer(char[] str, int arr[]) { // Sort the array Arrays.sort(arr); // Check if a character is present in // str that satisfies the condition boolean possible = false; // hash[i]: Check if character i // is present in arr[] or not boolean[] hash = checkChar(str); // Traverse all possible distinct // character of str for (int ch = 0; ch < 26; ch++) { // If ch present in str if (!hash[ch]) continue; // Find all the intervals for // current character List<SpecialInterval> intervals = findSpecialIntevals(str, (char)(ch + 'a')); // Update possible possible = checkIfValid(intervals, arr); // If a character found in str that // satisfies the condition if (possible) { System.out.println((char)(ch + 'a')); break; } } // If no character found that // satisfies the condition if (!possible) System.out.println(-1); } // Driver Code public static void main(String[] args) { char[] str = { 'a', 'b', 'c', 'a', 'e', 'a', 'a' }; int arr[] = { 4, 6 }; printAnswer(str, arr); }} |
Python3
# Structure of an intervalclass SpecialInterval: # Initialize a interval def __init__(self, low, high): self.low = low self.high = high# Function to check if a character# present in arr[] or notdef checkChar(s): # hash[i]: Check if character i # is present in arr[] or not hash = [False] * 26 # Traverse the character array for i in range(len(s)): # Mark arr[i] as true hash[ord(s[i]) - 97] = True return hash# Function to check if all the intervals of a# character satisfies the condition or notdef checkIfValid(intervals, arr): # If no intervals found for # the current character if len(intervals) == 0: return True # Sort intervals on increasing # order of start point intervals.sort(key=lambda x: x.low) # Store the intervals on increasing # order of end point of interval pq = [] # Stores count of array elements that # is present in different intervals count = 0 # Stores index of an interval j = 0 # Traverse the character array for i in range(len(arr)): if count >= len(intervals): break # Traverse intervals[] array while j < len(intervals): # Stores interval # at j-th index interval = intervals[j] # If start point of interval # greater than arr[i] if interval.low > arr[i]: break # Update j j += 1 # Insert interval into pq pq.append(interval) pq.sort(key=lambda x: x.high) # If count of intervals # in pq greater than 0 if len(pq) > 0: # Stores top element of pq interval = pq[0] pq.pop(0) # arr[i] does not lie in # the range of the interval if arr[i] > interval.high: break # Update count count += 1 return count == len(intervals)# Function to find the intervals# for each distinct character of str[]def findSpecialIntervals(s, ch): # Stores the odd index # of the character array oddPrev = -1 # Stores even index of # the character array evenPrev = -1 # Stores all intervals for each # distinct character of str intervals = [] # Traverse the character array for i in range(len(s)): if s[i] == ch: # If i is even if i % 2 == 0: # If evenPrev not # equal to -1 if evenPrev == -1: # Update evenPrev evenPrev = i else: # Initialize an interval interval = SpecialInterval(evenPrev, i) # Insert current interval # into intervals intervals.append(interval) # Update evenPrev evenPrev = -1 else: # If oddPrev not # equal to -1 if oddPrev == -1: # Update oddPrev oddPrev = i else: # Initialize an interval interval = SpecialInterval(oddPrev, i) # Insert current interval # into intervals intervals.append(interval) # Update oddPrev oddPrev = -1 return intervals# Function to print lexicographically smallest# character that satisfies the conditiondef printAnswer(strs, arr): # Sort the array arr.sort() # Check if a character is present in # str that satisfies the condition possible = False # hash[i]: Check if character i # is present in arr[] or not hash = checkChar(strs) # print(hash) # Traverse all possible distinct # character of str for ch in range(26): # If ch present in str if not hash[ch]: continue # Find all the intervals for # current character intervals = findSpecialIntervals(strs, chr(ch + 97)) # Update possible possible = checkIfValid(intervals, arr) # If a character found in str that # satisfies the condition if possible: print(chr(ch + 97)) break # If no character found that # satisfies the condition if not possible: print(-1)# Driver Codestrs = ['a', 'b', 'c', 'a', 'e', 'a', 'a']arr = [4, 6]printAnswer(strs, arr)# The code is contributed by phasing17 |
Javascript
// Javascript Program to implement// the above approach// Structure of an intervalclass SpecialInterval { // Initialize a interval constructor(low, high) { this.low = low; this.high = high; }}// Function to check if a character// present in arr[] or notfunction checkChar(str){ // hash[i]: Check if character i // is present in arr[] or not let hash = new Array(26); // Traverse the character array for (let i = 0; i < str.length; i++) { // Mark arr[i] as true hash[str[i].charCodeAt(0) - 97] = true; } return hash;}// Function to check if all the intervals of a// character satisfies the condition or notfunction checkIfValid(intervals, arr){ // If no intervals found for // the current character if (intervals.length == 0) { return true; } // Sort intervals on increasing // order of start point intervals.sort(function(a, b){ return a.low - b.low; }); // Store the intervals on increasing // order of end point of interval let pq = []; // Stores count of array elements that // is present in different intervals let count = 0; // Stores index of an interval let j = 0; // Traverse the character array for (let i = 0; i < arr.length && count < intervals.length; i++) { // Traverse intervals[] array while (j < intervals.length) { // Stores interval // at j-th index let interval = intervals[j]; // If start point of interval // greater than arr[i] if (interval.low > arr[i]) break; // Update j j++; // Insert interval into pq pq.push(interval); pq.sort(function(a, b){ return a.high - b.high; }); } // If count of intervals // in pq greater than 0 if (pq.length > 0) { // Stores top element of pq let interval = pq[0]; pq.shift(); // arr[i] does not lie in // the range of the interval if (arr[i] > interval.high) { break; } // Update count count++; } } return count == intervals.length;}// Function to find the intervals// for each distinct character of str[]function findSpecialIntevals(str, ch){ // Stores the odd index // of the character array let oddPrev = -1; // Stores even index of // the character array let evenPrev = -1; // Stores all intervals for each // distinct character of str let intervals = []; // Traverse the character array for (let i = 0; i < str.length; i++) { if (str[i] == ch) { // If i is even if (i % 2 == 0) { // If evenPrev not // equal to -1 if (evenPrev == -1) { // Update evenPrev evenPrev = i; } else { // Initialize an interval let interval = new SpecialInterval(evenPrev, i); // Insert current interval // into intervals intervals.push(interval); // Update evenPrev evenPrev = -1; } } else { // If oddPrev not // equal to -1 if (oddPrev == -1) { // Update oddPrev oddPrev = i; } else { // Initialize an interval let interval = new SpecialInterval( oddPrev, i); // Insert current interval // into intervals intervals.push(interval); // Update oddPrev oddPrev = -1; } } } } return intervals;}// Function to print lexicographically smallest// character that satisfies the conditionfunction printAnswer(str, arr){ // Sort the array arr.sort(); // Check if a character is present in // str that satisfies the condition let possible = false; // hash[i]: Check if character i // is present in arr[] or not let hash = checkChar(str); // Traverse all possible distinct // character of str for (let ch = 0; ch < 26; ch++) { // If ch present in str if (!hash[ch]) continue; // Find all the intervals for // current character let intervals = findSpecialIntevals(str, String.fromCharCode(ch + 97)); // Update possible possible = checkIfValid(intervals, arr); // If a character found in str that // satisfies the condition if (possible) { console.log(String.fromCharCode(ch + 97)); break; } } // If no character found that // satisfies the condition if (!possible) console.log(-1);}// Driver Codelet str = ['a', 'b', 'c', 'a', 'e', 'a', 'a'];let arr = [4, 6];printAnswer(str, arr);// The code is contributed by Arushi Jindal. |
C#
// C# code additionusing System;using System.Collections.Generic;using System.Linq;public class SpecialInterval { public int low; public int high; // Initialize an interval public SpecialInterval(int low, int high) { this.low = low; this.high = high; }}public class Program { // Function to check if a character // is present in arr[] or not public static bool[] CheckChar(char[] str) { // hash[i]: Check if character i // is present in arr[] or not bool[] hash = new bool[26]; // Traverse the character array for (int i = 0; i < str.Length; i++) { // Mark arr[i] as true hash[str[i] - 'a'] = true; } return hash; } // Function to check if all the intervals of a // character satisfies the condition or not public static bool CheckIfValid(List<SpecialInterval> intervals, int[] arr) { // If no intervals found for // the current character if (intervals.Count == 0) { return true; } // Sort intervals on increasing // order of start point intervals.Sort((a, b) = > a.low.CompareTo(b.low)); // Store the intervals on increasing // order of end point of interval List<SpecialInterval> pq = new List<SpecialInterval>(); // Stores count of array elements that // is present in different intervals int count = 0; // Stores index of an interval int j = 0; // Traverse the character array for (int i = 0; i < arr.Length && count < intervals.Count; i++) { // Traverse intervals[] array while (j < intervals.Count) { // Stores interval // at j-th index SpecialInterval interval = intervals[j]; // If start point of interval // greater than arr[i] if (interval.low > arr[i]) { break; } // Update j j++; // Insert interval into pq pq.Add(interval); pq.Sort((a, b) = > a.high.CompareTo(b.high)); } // If count of intervals // in pq greater than 0 if (pq.Count > 0) { // Stores top element of pq SpecialInterval interval = pq[0]; pq.RemoveAt(0); // arr[i] does not lie in // the range of the interval if (arr[i] > interval.high) { break; } // Update count count++; } } return count == intervals.Count; } // Function to find the intervals // for each distinct character of str[] public static List<SpecialInterval> FindSpecialIntervals(char[] str, char ch) { // Stores the odd index // of the character array int oddPrev = -1; // Stores even index of // the character array int evenPrev = -1; // Stores all intervals for each // distinct character of str List<SpecialInterval> intervals = new List<SpecialInterval>(); // Traverse the character array for (int i = 0; i < str.Length; i++) { if (str[i] == ch) { // If i is even if (i % 2 == 0) { // If evenPrev not // equal to -1 if (evenPrev == -1) { // Update evenPrev evenPrev = i; } else { // Initialize an interval var interval = new SpecialInterval( evenPrev, i); // Insert current interval // into intervals intervals.Add(interval); // Update evenPrev evenPrev = -1; } } else { // If oddPrev not // equal to -1 if (oddPrev == -1) { // Update oddPrev oddPrev = i; } else { // Initialize an interval var interval = new SpecialInterval( oddPrev, i); // Insert current interval // into intervals intervals.Add(interval); // Update oddPrev oddPrev = -1; } } } } return intervals; } // Function to print lexicographically smallest // character that satisfies the condition public static void printAnswer(char[] str, int[] arr) { // Sort the array Array.Sort(arr); // Check if a character is present in // str that satisfies the condition bool possible = false; // hash[i]: Check if character i // is present in arr[] or not bool[] hash = CheckChar(str); // Traverse all possible distinct // character of str for (int ch = 0; ch < 26; ch++) { // If ch present in str if (!hash[ch]) continue; // Find all the intervals for // current character List<SpecialInterval> intervals = FindSpecialIntervals(str, (char)(ch + 'a')); // Update possible possible = CheckIfValid(intervals, arr); // If a character found in str that // satisfies the condition if (possible) { Console.WriteLine((char)(ch + 'a')); break; } } // If no character found that // satisfies the condition if (!possible) Console.WriteLine(-1); } // Driver Code static void Main() { // Console.WriteLine("hi2"); char[] str = { 'a', 'b', 'c', 'a', 'e', 'a', 'a' }; int[] arr = { 4, 6 }; printAnswer(str, arr); }}// The code is contributed by Arushi Goel. |
Output:
a
Time Complexity: O(N * log(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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
