Statistics

Problem Statement for "PalindromeFactory"

Problem Statement

A palindrome is a string that reads the same forward and backward. Not all strings are palindromes and we are going to fix that.
In this problem we consider four edit operations:
  1. Insert a character at any position of a string (including the beginning and the end)
  2. Delete a character at any position of a string
  3. Change a character at any position of a string
  4. Swap any two different characters (not necessarily adjacent)

You can apply the first three operations any number of times, but the last operation can be applied at most once.

You are given a String initial. Return the minimal number of operations needed to make a palindrome from it.

Definition

Class:
PalindromeFactory
Method:
getEditDistance
Parameters:
String
Returns:
int
Method signature:
int getEditDistance(String initial)
(be sure your method is public)

Constraints

  • initial will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.

Examples

  1. "abba"

    Returns: 0

    The string is already a palindrome.

  2. "dabba"

    Returns: 1

    We can delete the first letter to make a palindrome.

  3. "babacvabba"

    Returns: 2

    Delete 'v' and swap the first two characters.

  4. "abc"

    Returns: 1

    We can change 'c' to 'a' to get a palindrome in one operation.

  5. "acxcba"

    Returns: 1

    Insert 'b' after the first character.

  6. "abcacbd"

    Returns: 1

    Swap 'd' with 'a' in the middle.

  7. "aaacaacbcabaaaabbabacacabbabacaacabbabcbabbaaacbaa"

    Returns: 8

  8. "idbifahfhalihlcfbdlabldkdefajaafdlkdbaigbbbeklfcbi"

    Returns: 18

  9. "gwucaltwaaliqgyamiubwmtyragjbyytuiacdeorlaabbkaynr"

    Returns: 18

  10. "jicaejceicfhhejaebab"

    Returns: 7

  11. "topcoder"

    Returns: 4

  12. "jajaaadafgfhajjjceah"

    Returns: 6

  13. "accbabb"

    Returns: 3

  14. "abcgefdgfecdba"

    Returns: 3

  15. "zyz"

    Returns: 0

  16. "xyz"

    Returns: 1

  17. "aaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 24

  18. "gugugugugugugugugugugugugu"

    Returns: 1

  19. "ppppppppppppsssssssssssssssuuuuuuuuuuu"

    Returns: 11

  20. "abcdefgrijklmnopqrstuvwxxwvutshqponmlkgjihgfedcba"

    Returns: 2

  21. "a"

    Returns: 0

  22. "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

    Returns: 0

  23. "abcdefggfedcbazx"

    Returns: 2

  24. "flagihjkbbfkjakeacfakgcdaadafeafbblbgefgbdjhhbhabj"

    Returns: 16

  25. "aablgbghieeehfaclijhajbcabfdibadjaclgffhehacldbcaa"

    Returns: 15

  26. "lfaggcdkheldafcagcflabahkfaiajaaigacdheccfdhdfhafl"

    Returns: 15

  27. "biliflakbackcagaeaialdclcidbclbicegfchifggbjaafleb"

    Returns: 15

  28. "aecagabaaebgbdefaeaaaaaggbcecaaeabedbggfbeaabadec"

    Returns: 10

  29. "aagagacgdgadgbecgdbaacadbadgcaedggadddagbgeaaagaa"

    Returns: 10

  30. "ccgcaaaddcafcdcdacgafacaeacggddgcagdadfgbddaagegc"

    Returns: 11

  31. "cceaabaccdaeaabdccbdcabbbaacdbbcdeaaadeadcabaacba"

    Returns: 8

  32. "aebcaeabbadcabeabacedaaadeaaaeecaeabacdeaebcaacbe"

    Returns: 8

  33. "dashklasdlkansclkjncsdjhflkasjdskajdsalkcalksask"

    Returns: 14

  34. "cuandolascosasfeasteatacannopuedesconetucodigofeo"

    Returns: 20

  35. "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"

    Returns: 23

  36. "abkanodfanogoandgaongoawenaohnoahnoaonho"

    Returns: 12

  37. "abcdefghijklmnopqrstuvwxyzabcdefg"

    Returns: 14

  38. "abcdefghijklmnopqrstuvwxyzabcdefghijklmpqrstuvwxyz"

    Returns: 23

  39. "abcdefghijklmnoprstuyvwxyzqw"

    Returns: 14

  40. "ecbbacad"

    Returns: 3

  41. "abcdefghijklmnopqrstuv"

    Returns: 11

  42. "abcdefghijklmnopqrstuvwxyz"

    Returns: 13

  43. "jghfffuiklllllllllllasdfghuwwwwwiasdjklllllljhgyub"

    Returns: 18

  44. "lfhajdheiwuqyrjsadhf"

    Returns: 7

  45. "bbcdefghijklmqopqrstuvwxyzyxwvutsrnponmlkjihgfedca"

    Returns: 3

  46. "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvw"

    Returns: 22

  47. "abcdefghijklmoqwertyuabcdefghijklmoqertycccvdcbak"

    Returns: 19

  48. "abcdeedcab"

    Returns: 1

  49. "ab"

    Returns: 1

  50. "iadoakjbfadlkjhfadiuksjdfbkadfkbvaadfkjadf"

    Returns: 15

  51. "amsdofozjzejfabmqsdjfazeopaozefjaqsdfmjsdqomfsdmsa"

    Returns: 16

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: