Shortest Palindrome in C++ (2024)

Table of Contents
Example Input Output FAQs

'; var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd(ad_id); });

Suppose we have a string s. We can convert it to palindrome by adding characters in front of it. We have to find the shortest palindrome, that we can find performing this information. So if the string is like “abcc”, then the result will be − "ccbabcc".

To solve this, we will follow these steps −

  • n := size of s, s1 := s, s2 := s

  • Reverse the string s2

  • s2 := s concatenate "#" concatenate s2

  • Define an array lps of size same as s2

  • j := 0, i := 1

  • while i < size of s2, do −

    • if s2[i] is same as s2[j], then,

      • lps[i] := j + 1

      • increase i by 1, increase j by 1

    • Otherwise

      • if j > 0, then, j := lps[j - 1]

      • Otherwise increase i by 1

  • extra := substring of s from lps[size of s – 1] to n - lps[size of lps - 1])

  • Reverse extra

  • return extra concatenate s

Example

Let us see the following implementation to get better understanding −

Live Demo

#include <bits/stdc++.h>using namespace std;class Solution { public: string shortestPalindrome(string s) { int n = s.size(); string s1 = s; string s2 = s; reverse(s2.begin(), s2.end()); s2 = s + "#" + s2; vector <int> lps(s2.size()); int j = 0; int i = 1; while(i <s2.size()){ if(s2[i] == s2[j]){ lps[i] = j + 1; j++; i++; } else { if(j > 0){ j = lps[ j - 1]; } else { i++; } } } string extra = s.substr(lps[lps.size() - 1], n - lps[lps.size() - 1]); reverse(extra.begin(), extra.end()); return extra + s; }};main(){ Solution ob; cout << (ob.shortestPalindrome("abcc"));}

Input

“abcc”

Output

ccbabcc

Updated on: 26-May-2020

521 Views

Kickstart Your Career

Get certified by completing the course

Get Started

Shortest Palindrome in C++ (31)

Advertisem*nts

';adpushup.triggerAd(ad_id); });

Shortest Palindrome in C++ (2024)

FAQs

What is the smallest string that is a palindrome? ›

Explanation 1:Change the last index “c” to “b”, it becomes “aabb”. Then rearrange the string, it becomes “abba”. This is the lexicographically smallest string.

How to do palindrome in C++? ›

Algorithm
  1. Declare a string A.
  2. If the string is empty then return true.
  3. Else, iterate over [0, N/2], using for loop and the variable i.
  4. Check if the character at (i and N-i-1) are not equal.
  5. If they are not the same, it is not Palindrome; if str[i] is always equal to str[N-i-1], then it is a palindrome.
Mar 26, 2024

What is the minimum character to make a string a palindrome? ›

For example, for the given string “deed”, the string is already a palindrome, thus, minimum characters needed are 0. Similarly, for the given string “aabaaca”, the minimum characters needed are 2 i.e. 'a' and 'c' which makes the string “acaabaaca” palindrome.

What is the longest palindrome? ›

The 19-letter Finnish word saippuakivikauppias (a soapstone vendor), is the longest single-word palindrome in everyday use, while the 12-letter term tattarrattat (from James Joyce in Ulysses) is the longest in English.

What is the smallest palindrome number? ›

The first 30 palindromic numbers (in decimal) are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...

What is the smallest 5 digit palindrome? ›

Continuing this process, we find that the smallest 5-digit palindrome using three different digits is option d. 10234. Therefore, the correct answer is d. 10234.

How to get the length of a string in C++? ›

You can obtain the length of a C++ string using the string class member functions length() or size() . Both of the methods return the data type size_t (which is an unsigned integer type), the number of valid characters in the string.

What is the Armstrong number in C++? ›

In the C programming language, an Armstrong number is a number that is equal to the sum of the cubes of its digits. For example, 153 is an Armstrong number because 1^3+ 5^3 + 3^3 = 153.

How do you reverse only words in a string in C++? ›

Method 4: Using stringstream and vector
  1. Create a stringstream from the given string.
  2. Create an empty vector to store the words of the sentence.
  3. Read each word from the stringstream and store it in the vector.
  4. Reverse each word in the vector.
  5. Concatenate the reversed words with a space between each word.
Jul 6, 2023

Is a 1 character string a palindrome? ›

We can think of a palindrome as just any sequence of letters that reads the same forward and backward, such as xyzyzyx. We call a sequence of letters a string. So we can say that any string containing just one letter is by default a palindrome.

How many 5 digit palindromes can be written? ›

By using multiplication principle, there are 9×10×10×1×1=900 5-digit palindromic numbers.

How many palindromes are there with 5 characters? ›

The answer is there are 17,576 five-character palindromes, if dups are allowed. How many five-letter words can be made from the 26 letters of the English language if repetition is allowed?

What is palindrome in C++? ›

Palindrome Program in C++

A number is a Palindrome number if the reverse of the number and the numbers itself are equal i.e. if the number and its reverse are the same then a number is a palindrome number. Example : Number : 12321 Reverse : 12321 Both number & reverse are equal so palindrome number.

What is the hardest palindrome? ›

The longest palindrome in English is often considered tattarrattat, coined by James Joyce in his 1922 Ulysses to imitate the sound of a knock on the door. Try your hand at this list of some of the hardest words to spell. That's 12 letters.

What is a word spelled backwards called? ›

A palindrome is a word or phrase that is the same forwards and backwards, but a semordnilap ("palindromes" backwards) is a word that becomes a different word when read backwards. Get it, smug gums? Heard in Unbreakable Kimmy Schmidt.

What is a string that is a palindrome? ›

A string is said to be palindrome if it remains the same on reading from both ends. It means that when you reverse a given string, it should be the same as the original string. For instance, the string 'level' is a palindrome because it remains the same when you read it from the beginning to the end and vice versa.

What is the smallest 3 digit palindrome number? ›

To create the three-digit palindromes, we must have identical, nonzero digits in the one's and hundred's places, but there is no restriction on the digit in the ten's place. The three digit palindromes are 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, . . .

Is empty string a palindrome? ›

Since an empty string reads the same forward and backward, it is a palindrome.

Top Articles
Latest Posts
Article information

Author: Ms. Lucile Johns

Last Updated:

Views: 5637

Rating: 4 / 5 (41 voted)

Reviews: 80% of readers found this page helpful

Author information

Name: Ms. Lucile Johns

Birthday: 1999-11-16

Address: Suite 237 56046 Walsh Coves, West Enid, VT 46557

Phone: +59115435987187

Job: Education Supervisor

Hobby: Genealogy, Stone skipping, Skydiving, Nordic skating, Couponing, Coloring, Gardening

Introduction: My name is Ms. Lucile Johns, I am a successful, friendly, friendly, homely, adventurous, handsome, delightful person who loves writing and wants to share my knowledge and understanding with you.