ಕ್ರಮಪಲ್ಲಟನೆಗಳೊಂದಿಗೆ ಪಾಲಿಂಡ್ರೋಮ್ ರೂಪಿಸಲು ಕನಿಷ್ಠ ಒಳಸೇರಿಸುವಿಕೆಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಕೋಡ್‌ನೇಷನ್ ಡೈರೆಕ್ಟಿ ಗೂಗಲ್ ವಾಸ್ತವವಾಗಿ ಪ್ರತ್ಯಕ್ಷ
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಸ್ಟ್ರಿಂಗ್

“ಕ್ರಮಪಲ್ಲಟನೆಗಳೊಂದಿಗೆ ಪಾಲಿಂಡ್ರೋಮ್ ರೂಪಿಸಲು ಕನಿಷ್ಠ ಒಳಸೇರಿಸುವಿಕೆಗಳು” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ಸಣ್ಣ ಅಕ್ಷರದಲ್ಲಿರುವ ಎಲ್ಲಾ ಅಕ್ಷರಗಳೊಂದಿಗೆ ಸ್ಟ್ರಿಂಗ್ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಒಂದು ಅಕ್ಷರವನ್ನು ಕನಿಷ್ಠ ಸ್ಟ್ರಿಂಗ್‌ಗೆ ಸೇರಿಸುವುದನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ, ಅದು ಪಾಲಿಂಡ್ರೋಮ್ ಆಗಬಹುದು. ಅಕ್ಷರಗಳ ಸ್ಥಾನವನ್ನು ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿ ಬದಲಾಯಿಸಬಹುದು.

ಉದಾಹರಣೆ

ಕ್ರಮಪಲ್ಲಟನೆಗಳೊಂದಿಗೆ ಪಾಲಿಂಡ್ರೋಮ್ ರೂಪಿಸಲು ಕನಿಷ್ಠ ಒಳಸೇರಿಸುವಿಕೆಗಳು

malyalam
1

ವಿವರಣೆ

ಆರಂಭಿಕ ಸ್ಟ್ರಿಂಗ್‌ಗೆ ನಾವು 'ಎ' ಅನ್ನು ಸೇರಿಸಬಹುದಾದರೆ, ನಾವು ಪಾಲಿಂಡ್ರೋಮ್ ಅನ್ನು ರಚಿಸಬಹುದು.

madaam
1

ವಿವರಣೆ

ಮೂಲ ಸ್ಟ್ರಿಂಗ್ ಪಾಲಿಂಡ್ರೋಮ್ ಮಾಡಲು 'ಡಿ' ಅಥವಾ 'ಎ' ಸೇರಿಸಿ.

ಕ್ರಮಾವಳಿ

  1. ಸ್ಟ್ರಿಂಗ್‌ನ ಉದ್ದವನ್ನು ಹೊಂದಿಸಿ l ಮತ್ತು output ಟ್‌ಪುಟ್ 0 ಕ್ಕೆ.
  2. ಒಂದು ಘೋಷಿಸಿ ಪೂರ್ಣಾಂಕ ಸರಣಿ.
  3. ಪ್ರತಿಯೊಂದು ಪಾತ್ರದ ಎಣಿಕೆಯನ್ನು ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ನಿರ್ವಹಿಸಿ.
  4. 0 ರಿಂದ ಪ್ರಾರಂಭಿಸಿ ನಾನು <26 ರವರೆಗೆ ರಚನೆಯನ್ನು ಹಾದುಹೋಗಿರಿ.
    1. ಪರಿಶೀಲಿಸಿ ಕೌಂಟ್ಚಾರ್ [i] % 2 == 1,
      1. ನಿಜವಾಗಿದ್ದರೆ, output ಟ್‌ಪುಟ್ ++ ಮಾಡಿ.
  5. Output ಟ್‌ಪುಟ್ 0 ಕ್ಕೆ ಸಮನಾಗಿದ್ದರೆ, 0 ಅನ್ನು ಹಿಂತಿರುಗಿ.
  6. ಬೇರೆ ರಿಟರ್ನ್ output ಟ್‌ಪುಟ್ -1.

ವಿವರಣೆ

ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಸ್ಟ್ರಿಂಗ್, ನಿಮ್ಮ ಕಾರ್ಯವು ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿ ಮಾಡಬೇಕಾದ ಕನಿಷ್ಠ ಒಳಸೇರಿಸುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದರಿಂದ ಅದು ಪಾಲಿಂಡ್ರೋಮ್ ಆಗುತ್ತದೆ. ಅಕ್ಷರಗಳ ಸ್ಥಾನವನ್ನು ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿ ಬದಲಾಯಿಸಬಹುದು. ನಾವು ಸ್ಟ್ರಿಂಗ್‌ನ ಪಾತ್ರದ ಸಂಭವವನ್ನು ಎಣಿಸಲು ಮತ್ತು ಅದನ್ನು ಒಂದು ಶ್ರೇಣಿಗೆ ಸಂಗ್ರಹಿಸಲಿದ್ದೇವೆ. ಏಕೆಂದರೆ ಹಿಂದಿನ ಆಲೋಚನೆಯೆಂದರೆ, ಸ್ಟ್ರಿಂಗ್ ಪಾಲಿಂಡ್ರೋಮ್ ಆಗಿದ್ದಾಗ, ಸ್ಟ್ರಿಂಗ್ ಉದ್ದವು ಬೆಸವಾಗಿದ್ದಾಗ ಒಂದೇ ಅಕ್ಷರ ಮಾತ್ರ ಬೆಸವಾಗಿರುತ್ತದೆ. ಅದನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಅಕ್ಷರಗಳು ಸಹ ಆವರ್ತನವನ್ನು ಹೊಂದಿವೆ. ಆದ್ದರಿಂದ ಬೆಸ ಸಂಖ್ಯೆಯ ಬಾರಿ ಸಂಭವಿಸುವ ಅಕ್ಷರಗಳನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕು.

ನಾವು ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಅಕ್ಷರಗಳನ್ನು ಎಣಿಸಿ ಅದನ್ನು ಶ್ರೇಣಿಗೆ ಸಂಗ್ರಹಿಸಲಿದ್ದೇವೆ. ನಾವು ಈಗಾಗಲೇ ಹೇಳಿದಂತೆ, ಪಾಲಿಂಡ್ರೋಮ್ ಆಗಿರುವ ಸ್ಟ್ರಿಂಗ್ ಒಂದು ಅಕ್ಷರವನ್ನು ಮಾತ್ರ ಹೊಂದಿರಬಹುದು ಅದು ಬೆಸ ಸಂಖ್ಯೆಯ ಬಾರಿ ಸಂಭವಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ .ಟ್‌ಪುಟ್ ಅಕ್ಷರ ಎಣಿಕೆಗಿಂತ ಒಂದು ಕಡಿಮೆ ಇರುತ್ತದೆ. ಪ್ರತಿಯೊಂದು ಅಕ್ಷರ ಸ್ಟ್ರಿಂಗ್ ಸಂಭವಿಸುವಿಕೆಯನ್ನು ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿದ ನಂತರ. ನಾವು ನಂತರ i = 0 ರಿಂದ i ಗೆ 26 ಕ್ಕಿಂತ ಕಡಿಮೆ ಇರುವ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಮಾಡುತ್ತಿದ್ದೇವೆ. ಇದಕ್ಕೆ ಕಾರಣ ಒಟ್ಟು 26 ಅಕ್ಷರಗಳಿವೆ ಮತ್ತು ನಿರ್ದಿಷ್ಟ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿ 26 ಅಕ್ಷರಗಳು ಸಂಭವಿಸುವ ಸಂಭವನೀಯತೆ ಇರುತ್ತದೆ ಎಂದು ನಾವು ಭಾವಿಸಬೇಕು.

ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುವಾಗ, ಪ್ರತಿ ಎಣಿಕೆಯನ್ನು 2 ರಿಂದ ಭಾಗಿಸಿದರೆ ಅದು ಉಳಿದಿದ್ದರೆ ಉಳಿದ 1 ಅನ್ನು ಬಿಡುತ್ತದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ನಂತರ ಅದು output ಟ್‌ಪುಟ್‌ನ ಸಂಖ್ಯೆಯನ್ನು 1 (output ಟ್‌ಪುಟ್ ++) ಹೆಚ್ಚಿಸುತ್ತದೆ. ಒಂದು ಶ್ರೇಣಿಯನ್ನು ದಾಟಿದ ನಂತರ, ಎಣಿಕೆ ಶೂನ್ಯವಾಗಿ ಉಳಿದಿದ್ದರೆ, ಅಂದರೆ ನಾವು ಬೆಸ ಅಕ್ಷರದಲ್ಲಿ ಏನನ್ನೂ ಕಾಣುವುದಿಲ್ಲ ಎಂದರೆ ಸ್ಟ್ರಿಂಗ್ ಈಗಾಗಲೇ ಪಾಲಿಂಡ್ರೋಮ್ ಆಗಿದೆ, ನಾವು 0 ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ, ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಹಿಂದಿರುಗುತ್ತೇವೆ (output ಟ್‌ಪುಟ್ -1) ನಾವು ಈಗಾಗಲೇ ಹೇಳಿದಂತೆ output ಟ್‌ಪುಟ್ ಒಂದಕ್ಕಿಂತ ಕಡಿಮೆ ಇರುತ್ತದೆ ಅಕ್ಷರ ಎಣಿಕೆ ಮತ್ತು ಆದ್ದರಿಂದ ನಮಗೆ got ಟ್‌ಪುಟ್ ಸಿಕ್ಕಿದೆ.

ಕೋಡ್

ಕ್ರಮಪಲ್ಲಟನೆಗಳೊಂದಿಗೆ ಪಾಲಿಂಡ್ರೋಮ್ ರೂಪಿಸಲು ಕನಿಷ್ಠ ಒಳಸೇರಿಸುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#include<iostream>

using namespace std;

int getMinimumInsertion(string str)
{
    int l = str.length(),output = 0;

    int countChar[26] = { 0 };
    for (int i = 0; i < l; i++)
        countChar[str[i] - 'a']++;

    for (int i = 0; i < 26; i++)
        if (countChar[i] % 2 == 1)
            output++;

    return (output == 0) ? 0 : output - 1;
}
int main()
{
    string str = "malyalam";
    cout << getMinimumInsertion(str);

    return 0;
}
1

ಕ್ರಮಪಲ್ಲಟನೆಗಳೊಂದಿಗೆ ಪಾಲಿಂಡ್ರೋಮ್ ರೂಪಿಸಲು ಕನಿಷ್ಠ ಒಳಸೇರಿಸುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

class insertionToPalindrome
{
    public static int getMinimumInsertion(String str)
    {
        int l = str.length(),output = 0;

        int countChar[] = new int[26];

        for (int i = 0; i < l; i++)
            countChar[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
        {
            if (countChar[i] % 2 == 1)
                output++;
        }

        return (output == 0) ? 0 : output - 1;
    }
    public static void main(String[] args)
    {
        String str = "malyalam";
        System.out.println(getMinimumInsertion(str));
    }
}
1

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿನ ಅಕ್ಷರಗಳ ಸಂಖ್ಯೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ಏಕೆಂದರೆ ನಾವು ಸ್ಥಿರ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುವ ಹೆಚ್ಚುವರಿ ಶ್ರೇಣಿಯನ್ನು ರಚಿಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.