Skip to Main Content
  • Questions

  • How to find possible combination of palindrome in a string

Breadcrumb

Question and Answer

Connor McDonald

Thanks for the question, anurag.

Asked: November 20, 2015 - 9:40 am UTC

Last updated: November 20, 2015 - 11:42 pm UTC

Version: Oracle 12c

Viewed 1000+ times

You Asked

Hi,
Is there any easy and optimize way to find the most possible no of palindrome in a string. String could be 1000 chars.

Thanks in advance.

and Connor said...

This *could* be done with pure SQL, but the reality is, that would be

a) probably more complex to read and maintain, and
b) somewhat wasted exercise because we have to call UTL_RAW anyway.

People may say "Hey, use the REVERSE function in SQL", but since its not documented...you're on a slippery slope there.

So here's a simple PLSQL routine to do it - you can pass whether you want them all, or just the largest one(s).


SQL> create or replace
  2  type str_list is table of varchar2(4000);
  3  /

Type created.

SQL>
SQL> create or replace
  2  function list_palindromes(p_str varchar2, p_largest_only varchar2 default 'N') return str_list pipelined is
  3    l_str_len int := length(p_str);
  4    
  5    l_candidate varchar2(1000);
  6    l_found boolean := false;
  7  begin
  8    for i in reverse 2 .. l_str_len 
  9    loop
 10      for j in 1 .. l_str_len - i + 1
 11      loop
 12        l_candidate := substr(p_str,j,i);
 13        if upper(l_candidate) = utl_raw.cast_to_varchar2( utl_raw.reverse ( utl_raw.cast_to_raw(upper(l_candidate)))) then
 14          pipe row (l_candidate);
 15          l_found := true;
 16        end if;
 17      end loop;
 18      if p_largest_only = 'Y' then
 19         exit when l_found;
 20      end if;
 21    end loop;
 22  end;
 23  /

Function created.

SQL> sho err
No errors.
SQL>
SQL> select * from table(list_palindromes(p_str=>'abaxyzaghjkkjhga'));

COLUMN_VALUE
----------------------------------------------------------------------------------------------------------------------------------
ghjkkjhg
hjkkjh
jkkj
aba
kk

5 rows selected.

SQL>
SQL> select * from table(list_palindromes(p_str=>'abaxyzaghjkkjhga',p_largest_only=>'Y'));

COLUMN_VALUE
----------------------------------------------------------------------------------------------------------------------------------
ghjkkjhg

1 row selected.



Rating

  (3 ratings)

Is this answer out of date? If it is, please let us know via a Comment

Comments

Just for the fun of it ...

cd, November 20, 2015 - 11:00 am UTC

I would second that solution. Only out of curiosity I decided to try the SQL/reverse function approach.

WITH t  AS (SELECT 'abaxyzaghjkkjhga' str
              FROM dual
           )
   , t1 AS (SELECT str
                 , ROWNUM pos
              FROM t
              CONNECT BY LEVEL < LENGTH(str) 
            )
SELECT substr(t2.str, t2.pos, t3.pos - t2.pos) palindrome  
 FROM t1 t2
    , t1 t3
WHERE t3.pos > t2.pos + 1
  AND substr(t2.str, t2.pos, t3.pos - t2.pos) = REVERSE(substr(t2.str, t2.pos, t3.pos - t2.pos))
order by t3.pos - t2.pos desc

And I have to add a bug fix right away ... ;-)

cd, November 20, 2015 - 11:05 am UTC

Sorry, my bad ...

WITH t  AS (SELECT 'abaxyzaghjkkjhga' str
              FROM dual
           )
   , t1 AS (SELECT str
                 , ROWNUM pos
              FROM t
              CONNECT BY LEVEL <= LENGTH(str) -- <- bugfix
            )
SELECT substr(t2.str, t2.pos, t3.pos - t2.pos) palindrome  
  FROM t1 t2
     , t1 t3
 WHERE t3.pos > t2.pos + 1
   AND substr(t2.str, t2.pos, t3.pos - t2.pos) = REVERSE(substr(t2.str, t2.pos, t3.pos - t2.pos))
  ORDER by t3.pos - t2.pos desc 
;

PALINDROME     
----------------
ghjkkjhg        
hjkkjh          
jkkj            
aba             
kk

And now it's getting embarressing ...

cd, November 20, 2015 - 11:20 am UTC

Serves me right that I didn't test the obvios case, a palindrome that takes the whole string length. Final version and sorry for the previous spam. 

WITH t  AS (SELECT 'palindromeemordnilap' str
              FROM dual
           )
   , t1 AS (SELECT str
                 , ROWNUM pos
              FROM t
              CONNECT BY LEVEL <= LENGTH(str) -- <- bugfix
            )
SELECT substr(t2.str, t2.pos, t3.pos - t2.pos + 1) palindrome  
  FROM t1 t2
     , t1 t3
 WHERE t3.pos > t2.pos 
   AND substr(t2.str, t2.pos, t3.pos - t2.pos + 1) = REVERSE(substr(t2.str, t2.pos, t3.pos - t2.pos + 1))
 ORDER by t3.pos - t2.pos desc 

PALINDROME         
--------------------
palindromeemordnilap
alindromeemordnila  
lindromeemordnil    
indromeemordni      
ndromeemordn        
dromeemord          
romeemor            
omeemo              
meem                
ee

Connor McDonald
November 20, 2015 - 11:42 pm UTC

Thats ok - I made an edit to mine as well once I found a bug.

In my case, no-one else has to see my history though :-)
more

Connor and Chris don't just spend all day on AskTOM. You can also catch regular content via Connor's blog and Chris's blog. Or if video is more your thing, check out Connor's channel and Chris's channel from their Youtube channels. And of course, keep up to date with AskTOM via the official twitter account.

More to Explore

PL/SQL demos

Check out more PL/SQL tutorials on our LiveSQL tool.

PL/SQL docs

PL/SQL reference manual from the Oracle documentation library