పాలిండ్రోమ్ సబ్‌స్ట్రింగ్ ప్రశ్నలు  


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది అమెజాన్ ByteDance eBay Expedia ద్వారా గూగుల్ Intuit మైక్రోసాఫ్ట్ పేపాల్ Pinterest Synopsys
డైనమిక్ ప్రోగ్రామింగ్ హ్యాషింగ్ ప్రశ్న సమస్య స్ట్రింగ్

సమస్యల నివేదిక  

“పాలిండ్రోమ్ సబ్‌స్ట్రింగ్ ప్రశ్నలు” సమస్య మీకు స్ట్రింగ్ మరియు కొన్ని ప్రశ్నలు ఇవ్వబడిందని పేర్కొంది. ఆ ప్రశ్నలతో, ఆ ప్రశ్న నుండి ఏర్పడిన సబ్‌స్ట్రింగ్ ఒక పాలిండ్రోమ్ కాదా అని మీరు నిర్ణయించుకోవాలి.

ఉదాహరణ  

String str = "aaabbabbaaa"

Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} }
The Substring [2 3] is not a palindrome

The Substring [2 8] is a palindrome

The Substring [5 7] is not a palindrome

The Substring [3 7] is a palindrome

వివరణ: సబ్‌స్ట్రింగ్ [2,8] ఒక పాలిండ్రోమ్, అందువలన ఫలితం అవును. సబ్‌స్ట్రింగ్ “అబ్బాబ్బా”.

అప్రోచ్  

ప్రతి ప్రశ్న ఆధారంగా మేము స్ట్రింగ్ మరియు కొన్ని ప్రశ్నలను ఇచ్చాము. అలా ఏర్పడిన సబ్‌స్ట్రింగ్‌ను మనం నిర్ణయించాలి a పాలిండ్రోమ్ లేదా. స్ట్రింగ్ ఉపయోగించండి హ్యాషింగ్ దీనిని పరిష్కరించడానికి. అసలు స్ట్రింగ్ కోసం ఒకటి మరియు రివర్స్డ్ స్ట్రింగ్ కోసం ఒకటి మేము రెండు శ్రేణులను ఉపయోగించబోతున్నాము. అప్పుడు మేము స్ట్రింగ్ యొక్క హాష్ విలువలను నిల్వ చేస్తాము. ఇక్కడ హాష్ విలువ ఒకదానికొకటి భిన్నంగా ఉంటుంది. మేము స్ట్రింగ్ కోసం హాష్ విలువను [] మరియు రివర్స్డ్ స్ట్రింగ్ కోసం రివర్స్ హాష్ విలువను తీసుకుంటున్నామని అనుకుందాం. మేము ఉపసర్గ మరియు ప్రత్యయం శ్రేణులను తీసుకుంటాము.

మనకు స్ట్రింగ్ స్ట్రింగ్ ఉందని అనుకుందాం: “అబ్బాబాబాఆ”.

మేము str యొక్క హాష్ విలువలను నిల్వ చేస్తాము

ఉపసర్గ [i] = str [0] + str [1] * 101 + str [2] * 1012  + ………. + Str [i-1] * 101 *i-1  .

ఉపసర్గ యొక్క ప్రతి విలువకు [i]. మేము ఈ క్రింది విలువలను కలిగి ఉంటాము:

Prefix[0]=0,
Prefix[1]= 97 + 97 *101, ( 0+ ASCII value of a)
Prefix[2]= 97 + 97 *101 + 98 *101^2
Prefix[3]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b).
.
.
.
Prefix [12]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 +…… +97 *101^11 as length of String is 12.

 

ఇది కూడ చూడు
అన్ని పాయింట్లను సందర్శించే కనీస సమయం లీట్‌కోడ్ పరిష్కారం

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

హాష్ విలువ (ఎడమ, కుడి) = ఉపసర్గ [కుడి + 1] - ఉపసర్గ [ఎడమ].

ఎడమ మరియు కుడి ప్రారంభ స్థానం, మేము స్ట్రింగ్ (2, 4) = “బిబిబి” యొక్క హాష్ విలువను కనుగొనాలనుకుంటే, అది ఇలా ఉంటుంది:

ఉపసర్గ [5] - ఉపసర్గ [2] = 98 * 1013 + 98 * 1014 + 98 * 1015.

ఈ విలువ పాలిండ్రోమ్‌ను కనుగొనడంలో సహాయపడుతుంది. ఎందుకంటే అదే మేము ప్రత్యయం శ్రేణితో చేస్తాము, కాని ఈసారి చివరి నుండి, ఎలా చూద్దాం.

స్ట్రింగ్ స్ట్రింగ్: “అబ్బాబాబాఆ”.

suffix[i] = str[n-1]+ str[n-2] *101 + str[n-3]*1022  + ……….+ str[n-i]*101*i-1  .
suffix[0]=0,
suffix [1]= 97 + 97 *101, ( 0+ ASCII value of a)
suffix [2]= 97 + 97 *101 + 97 *101^2,
suffix [3]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b).
.
.
.
.
suffix [11]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 +…… +97 *101^10 as length of String is 11.

ఇప్పుడు మనం ఉపయోగించి రివర్స్ హాష్ విలువ యొక్క విలువను లెక్కించవచ్చు:

రివర్స్ హాష్ విలువ (ఎడమ, కుడి): హాష్ విలువ (కుడి, ఎడమ) = ప్రత్యయం [n- ఎడమ] - ప్రత్యయం [n-Right-1].

ఉదాహరణ

ఉదాహరణకు: స్ట్రింగ్ str: “aabbbababaaa”.

రివర్స్ హాష్ విలువ: సబ్‌స్ట్రింగ్ (2,4):

“Bbba” విలువను తిప్పికొట్టడం “abbb”

ప్రత్యయం [11-1] - ప్రత్యయం [11-4-1] = ప్రత్యయం [10] -సఫిక్స్ [6].

పాలిండ్రోమ్ ఉనికిలో ఉందో లేదో తెలుసుకోవడానికి ఇప్పుడు మనకు ఒక సమీకరణం ఉంది.

ఇప్పుడు మనకు ఉపసర్గ మరియు ప్రత్యయం వలె రెండు శ్రేణులు ఉన్నాయి, వాటి మధ్య మాకు సంబంధం ఉంది.

(ఉపసర్గ [కుడి + 1] - ఉపసర్గ [ఎడమ])  =  (ప్రత్యయం [n - ఎడమ] - ప్రత్యయం [n - కుడి- 1])

ఇది కూడ చూడు
ప్రస్తుత సంఖ్య లీట్‌కోడ్ పరిష్కారం కంటే ఎన్ని సంఖ్యలు చిన్నవి

(101ఎడమ) (101n - కుడి - 1)

 

పాలిండ్రోమ్ సబ్‌స్ట్రింగ్ ప్రశ్నలుపిన్  

కోడ్  

పాలిండ్రోమ్ సబ్‌స్ట్రింగ్ ప్రశ్నల కోసం సి ++ కోడ్

#include<iostream>

using namespace std;

#define p 101
#define MOD 1000000007

struct Queries
{
    int left, right;
};
bool CheckPalindrome(string str, int left, int right)
{
    while (right > left)
        if (str[left++] != str[right--])
            return (false);
    return (true);
}
unsigned long long int moduloPower(unsigned long long int base,unsigned long long int exponent)
{
    if (exponent == 0)
        return 1;
    if (exponent == 1)
        return base;

    unsigned long long int temp = moduloPower(base, exponent / 2);

    if (exponent % 2 == 0)
        return (temp % MOD * temp % MOD) % MOD;
    else
        return (((temp % MOD * temp % MOD) % MOD)* base % MOD)% MOD;
}

unsigned long long int ModuloMultiplicativeInverse(unsigned long long int n)
{
    return moduloPower(n, MOD - 2);
}

void HashPrefix( string str, int n, unsigned long long int prefix[], unsigned long long int powerArr[])
{
    prefix[0] = 0;
    prefix[1] = str[0];

    for (int i = 2; i <= n; i++)
        prefix[i] = (prefix[i - 1] % MOD + (str[i - 1] % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;

    return;
}

void HashSuffix( string str, int n, unsigned long long int suffix[], unsigned long long int powerArr[])
{
    suffix[0] = 0;
    suffix[1] = str[n - 1];

    for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
        suffix[j] = (suffix[j - 1] % MOD+ (str[i] % MOD* powerArr[j - 1] % MOD)% MOD)% MOD;

    return;
}
void GetQueryOutput(string str, Queries q[], int m, int n, unsigned long long int prefix[], unsigned long long int suffix[], unsigned long long int powerArr[])
{
    for (int i = 0; i <= m - 1; i++)
    {
        int left = q[i].left;
        int right = q[i].right;

        unsigned long long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;

        unsigned long long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;

        if (HashValue == reverseHashValue)
        {
            if (CheckPalindrome(str, left, right) == true)
                cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
            else
                cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
        }

        else
            cout<<"The Substring ["<< left <<" "<<right<<"] is not a palindrome\n";
    }

    return;
}
void assginedPowers(unsigned long long int powerArr[], int n)
{
    powerArr[0] = 1;

    for (int i = 1; i <= n; i++)
        powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;

    return;
}
int main()
{
    string str = "aaabbabbaaa";
    int n = str.length();

    unsigned long long int powerArr[n + 1];

    assginedPowers(powerArr, n);

    unsigned long long int prefix[n + 1];
    unsigned long long int suffix[n + 1];

    HashPrefix(str, n, prefix, powerArr);
    HashSuffix(str, n, suffix, powerArr);

    Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} };
    int m = sizeof(q) / sizeof(q[0]);

    GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
    return (0);
}
The Substring [2 3] is not a palindrome
The Substring [2 8] is a palindrome
The Substring [5 7] is not a palindrome
The Substring [3 7] is a palindrome

పాలిండ్రోమ్ సబ్‌స్ట్రింగ్ ప్రశ్నల కోసం జావా కోడ్

public class PalindromeSubstringQuery
{
    static int p = 101;
    static int MOD = 1000000007;

    public static class Queries
    {
        int left, right;
        public Queries(int left, int right)
        {
            this.left = left;
            this.right = right;
        }
    }
    public static boolean CheckPalindrome(String str, int left, int right)
    {
        while (right > left)
        {
            if (str.charAt(left++) != str.charAt(right--))
                return (false);
        }
        return (true);
    }
    public static int moduloPower(int base, int exponent)
    {
        if (exponent == 0)
        {
            return 1;
        }
        if (exponent == 1)
        {
            return base;
        }
        int temp = moduloPower(base, exponent / 2);

        if (exponent % 2 == 0)
        {
            return (temp % MOD * temp % MOD) % MOD;
        }
        else
        {
            return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD;
        }
    }
    public static int ModuloMultiplicativeInverse(int n)
    {
        return moduloPower(n, MOD - 2);
    }

    public static void HashPrefix(String str, int n,int prefix[], int powerArr[])
    {
        prefix[0] = 0;
        prefix[1] = str.charAt(0);

        for (int i = 2; i <= n; i++)
        {
            prefix[i] = (prefix[i - 1] % MOD+ (str.charAt(i - 1) % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;
        }
        return;
    }
    public static void HashSuffix(String str, int n,int suffix[], int powerArr[])
    {
        suffix[0] = 0;
        suffix[1] = str.charAt(n - 1);

        for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
        {
            suffix[j] = (suffix[j - 1] % MOD + (str.charAt(i) % MOD* powerArr[j - 1] % MOD) 	% MOD) % MOD;
        }
        return;
    }
    public static void GetQueryOutput( String str, Queries q[], int m, int n, int prefix[], int suffix[], int powerArr[])
    {
        for (int i = 0; i <= m - 1; i++)
        {
            int left = q[i].left;
            int right = q[i].right;

            long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;

            long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;

            if (HashValue == reverseHashValue)
            {
                if (CheckPalindrome(str, left, right) == true)
                {
                    System.out.print("The Substring ["+left+" "+ right+"] is a palindrome\n");
                }
                else
                {
                    System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
                }
            }
            else
            {
                System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
            }
        }
        return;
    }
    public static void assginedPowers(int powerArr[], int n)
    {
        powerArr[0] = 1;

        for (int i = 1; i <= n; i++)
            powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;

        return;
    }
    public static void main(String[] args)
    {
        String str = "aaabbabbaaa";
        int n = str.length();

        int[] powerArr = new int[n + 1];

        assginedPowers(powerArr, n);

        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];

        HashPrefix(str, n, prefix, powerArr);
        HashSuffix(str, n, suffix, powerArr);

        Queries q[] = { new Queries(2, 3), new Queries(2, 8),new Queries(5, 7), new Queries(3, 7) };

        int m = q.length;

        GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
    }
}
The Substring [2 3] is not a palindrome
The Substring [2 8] is a palindrome
The Substring [5 7] is not a palindrome
The Substring [3 7] is a palindrome

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

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

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

ఇది కూడ చూడు
ఇచ్చిన మొత్తంతో సబ్‌రేను కనుగొనండి (ప్రతికూల సంఖ్యలను నిర్వహిస్తుంది)

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

పై) (ఇక్కడ  “ఎన్” ఇచ్చిన స్ట్రింగ్‌లోని అక్షరాల సంఖ్య. ఎందుకంటే మేము స్ట్రింగ్ కోసం హాష్ విలువలను నిల్వ చేసాము. మేము అదనపు స్థలాన్ని ఉపయోగించాము.