Find the last palindrome string in the given array

In this problem, we need to find the last palindrome string in the array. If any string is the same when read, whether it is read from the beginning or from the end, it is said that the string is a palindrome. We can compare the start and end characters to check if a particular string is a palindrome. Another way to find a palindrome string is to reverse the string and compare it to the original string.

Problem Statement - We are given an array of length N containing different strings. We need to find the last palindrome string in the given array.

Example Example

Input– arr[] = {"werwr", "rwe", "nayan", "tut", "rte"};

Output – ‘tut’

Explanation– The last palindrome string in the given array is ‘tut’.

Input– arr[] = {"werwr", "rwe", "nayan", "acd", "sdr"};

Output-"nayan"

Explanation – ‘nayan’ is the last palindrome string in the given array.

Input– arr[] = {"werwr", "rwe", "jh", "er", "rte"};

Output-""

Explanation – Since the array does not contain any palindrome string, it prints the empty string.

method 1

In this method, we will iterate through the array from the beginning and store the last palindrome string in a variable. Additionally, we compare the starting and ending characters of the string to check if the string is a palindrome.

algorithm

• Define variable 'lastPal' to store the last palindrome string.

• Traverse the array.

• Use the isPalindrome() function to check whether the string at the pth index in the array is a palindrome.

• In the isPalindrome() function, use a loop to traverse the string.

• Compares str[i] and str[len - p - 1] characters; if any characters do not match, return false.

• Return true after all iterations of the loop are completed.

• If the current string is a palindrome, update the value of the 'lastPal' variable with the current string.

• Return "lastPal".

Example

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string &str) {
   int size = str.length();
   for (int p = 0; p < size / 2; p++) {
      // compare first ith and last ith character
      if (str[p] != str[size - p - 1]) {
          return false;
      }
   }
   return true;
}
string LastPalindrome(string arr[], int N) {
   string lastPal = "";
   for (int p = 0; p < N; p++) {
      if (isPalindrome(arr[p])) {
          // if the current string is palindrome, then update the lastPal string
          lastPal = arr[p];
      }
   }
   return lastPal;
}
int main() {
   string arr[] = {"werwr", "rwe", "nayan", "abba", "rte"};
   int N = sizeof(arr)/sizeof(arr[0]);
   cout << "The last palindromic string in the given array is " << LastPalindrome(arr, N);
   return 0;
}

Output

The last palindromic string in the given array is abba

Time complexity - O(N*K), because we loop through the array and check if each string is a palindrome.

Space complexity - O(1), because we are using constant space.

Method 2

In this method we will iterate through the array starting from the last one and when we find the last palindrome string we will return it. Additionally, we use the reverse() method to check if the string is a palindrome.

algorithm

• Traverse the array starting from the last one.

• Use the isPalindrome() function to check whether the string is a palindrome.

• In the isPalindrome() function, store the 'str' string in the 'temp' variable.

• Use the reverse() method to reverse a temporary string.

• If str and temp are equal, return true. Otherwise, return false.

• If the string at the i-th index is a palindrome, return the string.

Example

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(string &str) {
    string temp = str;
    reverse(temp.begin(), temp.end());
    return str == temp;
}

string LastPalindrome(string array[], int N) {
    for (int p = N - 1; p >= 0; p--) {
        if (isPalindrome(array[p])) {
            return array[p];
        }
    }
    // Return a default value if no palindrome is found
    return "No palindromic string found";
}

int main() {
    string arr[] = {"werwr", "rwe", "nayan", "tut", "rte"};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The last palindromic string in the given array is " << LastPalindrome(arr, N);
    return 0;
}

Output

The last palindromic string in the given array is tut

Time complexity - O(N*K), since we iterate through the array and reverse the string.

Space complexity - O(1), because we don't use dynamic space.

Here, we learned two methods to find the last palindrome string in a given array. The time and space complexity of both methods are almost similar, but the second code is more readable and better than the first one.

Also, programmers can try to find the penultimate string in a given array and practice more.

The above is the detailed content of Find the last palindrome string in the given array. For more information, please follow other related articles on the PHP Chinese website!