Approach
We are given a String and a number of Queries, which contain some integer and character input values. We must change or replace the characters with the given character and at certain indices, i_1 and i_2, and then determine whether the string formed is a palindrome or not after each query performed.
The concept is to employ hashing. Set will be used to solve this problem. We will create two separate functions: one to accept queries and another to check palindromes. Essentially, that function operates in a bit-by-bit fashion. As a result of each call to that function.
It performs operations on Set and returns whether or not Set is empty. If it is empty, the string is a palindrome; otherwise, it is not.
Algorithm
-
Create a Set.
-
Set all the unequal indexes for the first half.
-
At the given index, replace the characters with the given character values (i_1 and i_2).
-
If i_1 > n/2, perform i_1=n-1-i_1 and if i_2 > n/2, perform i_2=n-1-i_2 respectively.
-
Now check if str[i_1] == str[n-1-i_1], if it is found to be true, then check if i_1 is present in a Set or not, and if it is present, remove it.
-
Otherwise, add i_1 to Set.
-
Repeat this procedure for i_2.
-
Rep step 3 until the total number of queries is reached.
- If Set is empty, it is a palindrome; otherwise, it is not.
Implementation in C++
//headers
#include<iostream>
#include<unordered_set>
using namespace std;
// palindrome checking function
void palindromeCheck(string &realstr, int index, int n,unordered_set<int> &SET)
{
if (realstr[index] == realstr[n-1-index])
{
if (SET.find(index) != SET.end())
SET.erase(SET.find(index)) ;
}
else
SET.insert(index);
}
void getQuery(string &realstr, int query)
{
//calculating length
int n = realstr.length();
unordered_set<int> SET;
for (int i=0; i<n/2; i++)
if (realstr[i] != realstr[n-1-i])
SET.insert(i);
for (int QueryNo=1; QueryNo<=query; QueryNo++)
{
//result output
cout << "Values for query " << QueryNo <<endl;
int i_1, i_2;
char ch;
cout << "Enter i_1 ";
cin >> i_1;
cout << "Enter i_2 ";
cin >> i_2;
cout << "Enter ch ";
cin >> ch;
realstr[i_1] = realstr [i_2] = ch;
if (i_1 > n/2)
i_1 = n- 1 -i_1;
if (i_2 > n/2)
i_2 = n -1 - i_2;
palindromeCheck(realstr, i_1, n, SET );
palindromeCheck(realstr, i_2, n, SET );
cout << "Output for query " << QueryNo << " => ";
SET.empty()? cout << "YES"<<endl<<endl : cout << "NO"<<endl<<endl;
}
}
//main function
int main()
{
//given string
string realstr = "india";
//query set
int query = 2 ;
//function pass
getQuery(realstr, query);
return 0;
}
Input
india
Output
Values for query 1
Enter i_1 0
Enter i_2 4
Enter ch i
Output for query 1 => NO
Values for query 2
Enter i_1 1
Enter i_2 3
Enter ch n
Output for query 2 => YES
You can also read about the Longest Consecutive Sequence.
Implementation in java
//java headers
import java.util.Scanner;
import java.util.HashSet;
//creat class
class CodingNinja
{
private static Scanner ob=new Scanner(System.in);
public static void checkPalindrome(String realstr, int i, int n,HashSet<Integer> SET)
{
if (realstr.charAt(i) == realstr.charAt(n-1-i))
{
if (SET.contains(i))
SET.remove(i) ;
}
else
SET.add(i);
}
// defining method
public static void Query(String realstr, int Q)
{
int n = realstr.length();
// hashset
HashSet<Integer> SET=new HashSet<>();
for (int i=0; i<n/2; i++)
if (realstr.charAt(i) != realstr.charAt(n-1-i))
SET.add(i);
//loop
for (int query=1; query<=Q; query++)
{
//printing loop
System.out.println("Values for query " + query);
int i_1, i_2;
char ch;
System.out.print("Enter i_1 " );
i_1=ob.nextInt();
System.out.print("Enter i_2 ");
i_2=ob.nextInt();
System.out.print("Enter ch ");
ch=ob.next().charAt(0);
char[] strChars = realstr.toCharArray();
strChars[i_1] = ch;
strChars[i_2] = ch;
str = String.valueOf(strChars);
if (i_1 > n/2)
i_1 = n- 1 -i_1;
if (i_2 > n/2)
i_2 = n -1 - i_2;
checkPalindrome(realstr, i_1, n, SET );
checkPalindrome(realstr, i_2, n, SET );
System.out.print("Output for query " + query + " => ");
if(SET.isEmpty())
System.out.println("YES\n\n");
else
System.out.println("NO\n");
}
}
//main function
public static void main(String args[])
{
//given string
String realstr = "india";
//query set
int query = 2 ;
Query(realstr, query);
}
}
Input
india
Output
Values for query 1
Enter i_1 0
Enter i_2 4
Enter ch i
Output for query 1 => NO
Values for query 2
Enter i_1 1
Enter i_2 3
Enter ch n
Output for query 2 => YES
Complexity
Time Complexity:
O(Q+N), where "Q" represents the number of queries and "N" represents the length of the string
Reason: Since we first run a loop until the string is half-length, add all unequal indices to map, and then compute the queries, which each take O(1) time. The complexity of time becomes linear.
Space Complexity:
O(N), Where ‘N’ stands for the string's length.
Reason: because we are mapping the elements of the input sequence. In the worst-case scenario, we could have unequal characters at all indices. We'll have to pay an O(N) space for this.
Check out this problem - Subarray With 0 Sum
Frequently asked questions
What is the purpose of the hash Set?
We can use HashSet in Java if we need to access elements randomly. Because hash codes are used to access elements in a hash table. An element's hashcode is a unique identifier that aids in identifying the element in a hash table. HashSet elements cannot be duplicated.
Why is HashSet the best search?
It employs the object's hash code, a quickly computed integer. This hash code attempts to be as evenly distributed across all possible object values. As a result, it can distribute the inserted values with a very low probability of conflict into an array (hashtable).
Is HashMap a type of array?
Internally, the HashMap employs an Array and uses a hash function to map labels to array indexes. Hashmap can be implemented in at least two ways: Array: A hash function is used to map a key to the array index value.
What is the distinction between a hash map and a hash table?
One of the primary distinctions between HashMap and Hashtable is that HashMap is non-synchronized while Hashtable is synchronised. This means that Hashtable is thread-safe and can be shared between multiple threads, whereas HashMap cannot be shared between multiple lines without proper synchronisation.
Is HashMap a type of interface?
HashMap in Java. The Java HashMap class implements the Map interface, which allows us to store key-value pairs with unique keys. If you try to insert the duplicate key, it will replace the corresponding key's element. The key index makes it simple to perform operations such as updating, deleting, etc.
Conclusion
This article has gone through a problem related to the HashSet. If you identify any errors or want to add more details about the above subject matter, kindly comment.
Recommended Readings:
Want to learn more about the Data Structure in java? Click here. Understand concepts related to the hashmap. It will clear the concept.
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?
Please go check out our Operating system course.
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Ninja, have a great time learning.
39+ registered 
