ప్రతి అక్షర పున ment స్థాపన ప్రశ్న తర్వాత పాలిండ్రోమ్ కోసం తనిఖీ చేయండి


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది అమెజాన్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> ఫ్లిప్కార్ట్ గూగుల్ నెట్ఫ్లిక్స్
హాష్ స్ట్రింగ్

“ప్రతి అక్షర పున ment స్థాపన ప్రశ్న తర్వాత పాలిండ్రోమ్ కోసం తనిఖీ చేయండి” అనే సమస్య మీకు ఇవ్వబడిందని అనుకుందాం స్ట్రింగ్ మరియు కాదు. ప్రశ్నలలో, ప్రతి ప్రశ్నకు రెండు ఉన్నాయి పూర్ణ సంఖ్య ఇన్పుట్ విలువలు i1 మరియు i2 మరియు 'ch' అని పిలువబడే ఒక అక్షర ఇన్పుట్. ఇచ్చిన స్టేట్మెంట్ 'ch' తో i1 మరియు i2 సూచికల వద్ద విలువలను మార్చమని మరియు ఇది పాలిండ్రోమ్ కాదా అని నిర్ణయించడానికి సమస్య స్టేట్మెంట్ అడుగుతుంది.

గమనిక: 0 <i1 కన్నా తక్కువ లేదా సమానం మరియు i2 స్ట్రింగ్ యొక్క పొడవు కంటే తక్కువ లేదా సమానం.

ఉదాహరణ

ప్రతి అక్షర పున ment స్థాపన ప్రశ్న తర్వాత పాలిండ్రోమ్ కోసం తనిఖీ చేయండి

String: india, Query=2.
Query 1: i1 = 0, i2 = 4, ch = i
Query 2: i1 = 1, i2 = 3, ch = n
Query 1: No
Query 2: Yes

వివరణ

ప్రశ్న 1: ఇండియా భర్తీ తర్వాత ఇండియా అవుతుంది

ప్రశ్న 2: ఇండిని భర్తీ చేసిన తర్వాత ఇండి అవుతుంది

String: english, Query=3.
Query 1: i1 = 0, i2 = 6, ch = e
Query 2: i1 = 1, i2 = 5, ch = s
Query 3: i1 = 2, i2 = 4, ch = i
Query 1: No
Query 2: No
Query 3: Yes

వివరణ

ప్రశ్న 1: పున eng స్థాపన తర్వాత ఇంగ్లీష్ అవుతుంది

ప్రశ్న 2: పున es స్థాపన తర్వాత ఇంగ్లీష్ అవుతుంది

ప్రశ్న 3: పున es స్థాపన ఎస్సైలైజ్ తర్వాత ఎస్గ్లైస్ అవుతుంది

అల్గారిథం

  1. ప్రకటించండి a సెట్.
  2. మొదటి సగం కోసం అన్ని అసమాన సూచికలను సెట్‌లో నిల్వ చేయండి.
  3. మార్చు అక్షరాలు ఇచ్చిన సూచిక (i1 మరియు i2) వద్ద ఇచ్చిన అక్షర విలువలతో.
    1. I1> n / 2 ఉంటే i1 = n-1-i1 మరియు i2> n / 2 చేయండి, నిజమైతే i2 = n-1-i2 చేయండి.
    2. ఇప్పుడు భర్తీ చేసిన తర్వాత str [i1] == str [n-1-i1], అది నిజమని తేలితే, i1 ఒక సెట్‌లో ఉందో లేదో తనిఖీ చేయండి, ఉన్నట్లయితే దాన్ని తీసివేస్తుంది.
      1. సెట్ చేయడానికి i1 ని జోడించండి.
    3. I2 కోసం ఈ విధానాన్ని పునరావృతం చేయండి.
  4. 3 వ దశ నుండి ఇచ్చిన మొత్తం ప్రశ్నల సంఖ్య వరకు పునరావృతం చేయండి.
  5. ఖాళీగా ఉంటే సెట్ చేస్తే అది పాలిండ్రోమ్, లేకపోతే అది కాదు.

వివరణ

మనకు ఒక స్ట్రింగ్ మరియు కొన్ని ప్రశ్నలు ఇవ్వబడ్డాయి, దీనిలో కొన్ని పూర్ణాంక మరియు అక్షర ఇన్పుట్ విలువలు ఉన్నాయి, ఇచ్చిన అక్షరాలతో అక్షరాలను మార్చాలి లేదా మార్చాలి మరియు కొన్ని సూచికల వద్ద i1 మరియు i2 గా ఇవ్వబడతాయి మరియు తరువాత మనకు అవసరమైన తరువాత ప్రతి ప్రశ్న నిర్వహించిన తర్వాత ఏర్పడిన స్ట్రింగ్ పాలిండ్రోమ్ కాదా అని నిర్ణయించడానికి. ఉపయోగించాలనే ఆలోచన ఉంది హాషింగ్. ఈ సమస్యను పరిష్కరించడానికి మేము సెట్‌ను ఉపయోగించబోతున్నాము. మేము ప్రత్యేక ఫంక్షన్ చేయబోతున్నాం ఒక ఫంక్షన్ ప్రశ్నలను తీసుకోవడం మరియు మరొక ఫంక్షన్ పాలిండ్రోమ్‌ను తనిఖీ చేయడం. సాధారణంగా, ఆ ఫంక్షన్ బిట్ ఫ్యాషన్ ద్వారా కొంచెం పనిచేస్తుంది. ప్రతి కాల్ కారణంగా మేము ఆ ఫంక్షన్‌కు చేస్తాము. ఇది సెట్‌లో కార్యకలాపాలను నిర్వహిస్తుంది మరియు సెట్ ఖాళీగా ఉందో లేదో మేము తనిఖీ చేసినప్పుడు. ఇది ఖాళీగా ఉంది అంటే స్ట్రింగ్ పాలిండ్రోమ్, లేకపోతే అది కాదు.

ఒక ఉదాహరణను పరిశీలిద్దాం:

ఉదాహరణ

స్ట్రింగ్: ఇండియా, ప్రశ్న = 2, అంటే ఇది i1, i2 మరియు ch యొక్క ఇన్పుట్లను 2 సార్లు తీసుకుంటుంది.

మేము స్ట్రింగ్ యొక్క మొదటి సగం యొక్క అసమాన సూచికలను నిల్వ చేయాలి

కాబట్టి మొత్తం స్ట్రింగ్‌ను దాటిన తరువాత, మనకు ఈ విధంగా సెట్ ఉంటుంది,

సెట్: [0, 1]

1 వ ప్రశ్న కోసం, i1 = 0, i2 = 4, ch = i, అంటే స్ట్రింగ్ “india” “indii” అవుతుంది.

i1 i1 గా 0 గా ఉంటుంది, i2 0 అవుతుంది, మొదట, i1 పాస్ అవుతుంది మరియు str [i1] == str [n-1-i1] అని తనిఖీ చేస్తుంది, ఇది నిజం, అప్పుడు i1 ఒక సెట్‌లో ఉందో లేదో తనిఖీ చేస్తుంది, అది ఇది కూడా ఉంది, కాబట్టి ఇది సెట్ నుండి i1 అంటే 0 ను తొలగిస్తుంది.

అప్పుడు i2 కూడా 0 కాబట్టి ఏమీ జరగదు.

2 వ ప్రశ్న కోసం, i1 = 1, i2 = 3, ch = n, అంటే స్ట్రింగ్ “indii” “indni” అవుతుంది.

i1 i1 గా 1 గా ఉంటుంది, i2 1 అవుతుంది, మొదట, i1 పాస్ అవుతుంది మరియు str [i1] == str [n-1-i1] అని తనిఖీ చేస్తుంది, ఇది నిజం, అప్పుడు i1 ఒక సెట్‌లో ఉందో లేదో తనిఖీ చేస్తుంది, అది ఇది కూడా ఉంది, కాబట్టి ఇది సెట్ నుండి i1 అంటే 1 ను తొలగిస్తుంది. ప్రదర్శించిన అన్ని ప్రశ్నల తరువాత సెట్ ఖాళీగా ఉందో లేదో తనిఖీ చేస్తుంది మరియు ఇప్పుడు అది ఖాళీగా ఉంది మరియు అది అవును అని ప్రింట్ చేస్తుంది ఎందుకంటే ఒక సెట్లో 0 మరియు 1 విలువలు రెండు ఉన్నాయి మరియు మేము ఈ రెండింటినీ తొలగించాము.

ప్రతి అక్షర పున ment స్థాపన ప్రశ్న తర్వాత పాలిండ్రోమ్ కోసం తనిఖీ చేయడానికి సి ++ కోడ్

#include<unordered_set>
#include<iostream>

using namespace std;
void checkPalindrome(string &str, int index, int n,unordered_set<int> &SET)
{
    if (str[index] == str[n-1-index])
    {
        if (SET.find(index) != SET.end())
            SET.erase(SET.find(index)) ;
    }
    else
        SET.insert(index);
}
void getQuery(string &str, int query)
{
    int n = str.length();
    unordered_set<int> SET;
    for (int i=0; i<n/2; i++)
        if (str[i] != str[n-1-i])
            SET.insert(i);

    for (int QueryNo=1; QueryNo<=query; QueryNo++)
    {
        cout << "Values for query " << QueryNo <<endl;
        int i1, i2;
        char ch;
        cout << "Enter i1 ";
        cin >> i1;
        cout << "Enter i2 ";
        cin >> i2;
        cout << "Enter ch ";
        cin >> ch;

        str[i1] = str [i2] = ch;

        if (i1 > n/2)
            i1 = n- 1 -i1;
        if (i2 > n/2)
            i2 = n -1 - i2;

        checkPalindrome(str, i1, n, SET );
        checkPalindrome(str, i2, n, SET );

        cout << "Output for query " << QueryNo << " => ";
        SET.empty()? cout << "YES"<<endl<<endl : cout << "NO"<<endl<<endl;
    }
}
int main()
{
    string str = "india";
    int query = 2 ;
    getQuery(str, query);
    return 0;
}
Values for query 1
Enter i1 0
Enter i2 4
Enter ch i
Output for query 1 => NO

Values for query 2
Enter i1 1
Enter i2 3
Enter ch n
Output for query 2 => YES

ప్రతి అక్షర పున ment స్థాపన ప్రశ్న తర్వాత పాలిండ్రోమ్ కోసం తనిఖీ చేయడానికి జావా కోడ్

import java.util.Scanner;
import java.util.HashSet;

class SearchPalindrome
{
    private static Scanner sc=new Scanner(System.in);
    public static void checkPalindrome(String str, int i, int n,HashSet<Integer> SET)
    {
        if (str.charAt(i) == str.charAt(n-1-i))
        {
            if (SET.contains(i))
                SET.remove(i) ;
        }
        else
            SET.add(i);
    }
    public static void Query(String str, int Q)
    {
        int n = str.length();
        HashSet<Integer> SET=new HashSet<>();
        for (int i=0; i<n/2; i++)
            if (str.charAt(i) != str.charAt(n-1-i))
                SET.add(i);

        for (int query=1; query<=Q; query++)
        {
      System.out.println("Values for query " + query);
            int i1, i2;
            char ch;
            System.out.print("Enter i1 " );
            i1=sc.nextInt();
            System.out.print("Enter i2 ");
            i2=sc.nextInt();
            System.out.print("Enter ch ");
            ch=sc.next().charAt(0);


            char[] strChars = str.toCharArray();
            strChars[i1] = ch;

            strChars[i2] = ch;
            str = String.valueOf(strChars);

            if (i1 > n/2)
                i1 = n- 1 -i1;
            if (i2 > n/2)
                i2 = n -1 - i2;

            checkPalindrome(str, i1, n, SET );
            checkPalindrome(str, i2, n, SET );

            System.out.print("Output for query " + query + " => ");

            if(SET.isEmpty())
                System.out.println("YES\n\n");
            else
                System.out.println("NO\n");
        }
    }
    public static void main(String args[])
    {
        String str = "india";
        int query = 2 ;
        Query(str, query);

    }
}
Values for query 1
Enter i1 0
Enter i2 4
Enter ch i
Output for query 1 => NO

Values for query 2
Enter i1 1
Enter i2 3
Enter ch n
Output for query 2 => YES

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (Q + N) (ఇక్కడ  "ప్ర" ప్రశ్నల సంఖ్య మరియు “ఎన్” స్ట్రింగ్ యొక్క పొడవు. మొదట మేము స్ట్రింగ్ యొక్క సగం పొడవు వరకు లూప్‌ను నడుపుతాము మరియు మ్యాప్‌కు అన్ని అసమాన సూచికలను జోడించి, ఆపై O (1) సమయం తీసుకునే ప్రశ్నలను గణించండి. సమయం సంక్లిష్టత సరళంగా మారుతుంది.

అంతరిక్ష సంక్లిష్టత

పై), ఎందుకంటే మేము ఇన్పుట్ సీక్వెన్స్ యొక్క అంశాలను మ్యాప్‌లోకి జతచేస్తున్నాము. మరియు చెత్త సందర్భంలో, మేము అన్ని సూచికల వద్ద అన్ని అసమాన అక్షరాలను కలిగి ఉండవచ్చు. ఇది మాకు O (N) స్థలాన్ని ఖర్చు చేస్తుంది.