Palindrome Problem - Minimum number of characters to make a text palindrome

Printable View

So, I'm having a very difficult task here. I need to analyze a certain text and find the minimum number of characters it needs to become a palindrome. The text will not have any special characters or numbers, just alphabet letters. Now, I've made some progression and have tried a lot of situations correctly, but in some situations I've gotten wrong outputs on the MINIMUM number of characters needed. I've tested the below texts:

AAABBBBCCCCC - AAABBBBCCCCCBBBBAAA ✓ 7
CCCCCBBBBAAA - AAABBBBCCCCCBBBBAAA ✓ 7
BBBBCCCCCAAA - AAABBBBCCCCCBBBBAAA ✓ 7
FASLLI - FAS-I-LLI-SAF ✓ 4
ARBEN - ARBEN-EBRA ✓ 4
ARBENA - ARBEN-EBR-A ✓ 3
ARBANA - ARBAN-ABR-A ✓ 3
ALL - ALL-A ✓ 1
ALLLL - ALLLL-A ✓ 1
BAOUB - BAOU-OA-B ✓ 2
ASDRFFF - ASDRFFF-DRSA ✓ 4
AAABBB - AAABBB-AAA / BBB-AAABBB ✓ 3
ARBENARBEN - ARBENARBEN-EBRANEBRA ✓ 9
ALLALL - ALLALL-A WRONG , outputs "4" when all there's needed is 1.
AAABBBBAAABBBBCCCCC - CCCCCBBBB-AAABBBBAAABBBBCCC WRONG, outputs 14 when all there's needed is 9 chars. In this case there should be noted that there are 2 palindromes within the text (as in substrings which may have something to do with the wrong output that I get, but I can't find what it is).

If anyone can help me with what is going wrong with the 2 cases in which the output is wrong I would appreciate it very very much. My code is below.

vb Code:

Public Class Form1
 
    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
 
        Dim counter As Integer = 0, counter2 As Integer = 0, temp As Integer = 0
        Dim Half As Integer
        Dim Test As Boolean = False
        RichTextBox1.Text = RichTextBox1.Text.Replace(" ", "")
        RichTextBox1.Text = RichTextBox1.Text.Replace(".", "")
        RichTextBox1.Text = RichTextBox1.Text.Replace(vbLf, "")
 
        Dim j As Integer = RichTextBox1.Text.Length
 
        If RichTextBox1.Text.Length Mod 2 Then
            ' just for help to test MsgBox("You've put an odd no. of Chars.")
            Half = Math.Floor((RichTextBox1.Text.Length - 1) / 2)
 
            For i = 0 To Half - 1
 
                For j = RichTextBox1.Text.Length - 1 To 0 Step -1
                    If i < Half Then
                        If RichTextBox1.Text.Chars(i) = RichTextBox1.Text.Chars(j) Then
                            MsgBox(RichTextBox1.Text.Chars(i) & RichTextBox1.Text.Chars(j))
                            counter = counter + 2
                        Else
                            MsgBox("Same chars at respective places are " & counter)
                            Test = True
                            MsgBox("Test became true")
                            Exit For
                        End If
                        i += 1
                    Else
                        'i += 1
                    End If
                    ' i = i + 1
                Next
 
                If Test = True Then Exit For
 
            Next
 
        Else
          ' just for help to test  MsgBox("You've put an even no. of Chars.")
            Half = Math.Floor((RichTextBox1.Text.Length) / 2)
            MsgBox(Half)
 
            For i = 0 To Half - 1
 
                For j = RichTextBox1.Text.Length - 1 To Half Step -1
                    If i < Half Then
                        If RichTextBox1.Text.Chars(i) = RichTextBox1.Text.Chars(j) Then
                            '            MsgBox(RichTextBox1.Text.Chars(i) & RichTextBox1.Text.Chars(j))
                            counter = counter + 2
 
                        Else
                            MsgBox("Same chars at respective places are " & counter)
                            Test = True
                            MsgBox("Test became true")
                            Exit For
                            '   j -= 1
                        End If
                        i += 1
                        '   Exit For
 
                    End If
 
                Next
 
                If Test = True Then Exit For
 
            Next
 
        End If
 
        If counter / 2 = Half Then
            MsgBox("This text is a palindrome, it doesn't need any additional character.")
        Else
 
            '     For j = RichTextBox1.Text.Length - 1 To 1 Step -1
            'If RichTextBox1.Text.Chars(j) = RichTextBox1.Text.Chars(j - 1) Then
 
           For i = 0 To RichTextBox1.Text.Length - 2
                If RichTextBox1.Text.Chars(i + 1) = RichTextBox1.Text.Chars(i) Then
                    counter2 = counter2 + 1
                    MsgBox("The no. of same straight chars atm is " & counter2)
                    If temp <= counter2 Then
                        temp = counter2
                        MsgBox("Biggest same straight char no. is " & temp)
                    End If
 
                    MsgBox(counter2)
                Else
                    counter2 = 0
                    End If
 
            Next
            If counter2 <= temp Then
                counter2 = temp
            End If
            MsgBox("Temp =" & temp)
 
            MsgBox("This text is not a palindrome, it needs " & (RichTextBox1.Text.Length - 1 - counter - temp) & " chars to become one.")
        End If
        'MsgBox(counter)
 
    End Sub
 
End Class

Re: Palindrome Problem - Minimum number of characters to make a text palindrome

This works for every case you add characters to the beginning or to the end of the string in direct and reverse order. This won't be working if you wish to include cases when characters are added in the middle. In fact, I think it'll be too many iterations to check all the possibilities.
For example, this will return 4 for BAOUB

vb.net Code:

'
    Private Function CountCharsToPalyndrome(ByVal text As String) As Integer
        Dim addeddirect As String = text
        Dim addedreverse As String = New String(text.AsEnumerable.Reverse().ToArray())
        Dim returnval As Integer = addeddirect.Length
        ' Direct order, cutting from the end
        Dim teststring As String
        Dim charscut As Integer = 1
        Do While charscut < text.Length
            ' Direct order, cutting from the end
            teststring = addeddirect.Substring(0, addeddirect.Length - charscut)
            If IsPalyndrome(teststring & text) OrElse IsPalyndrome(text & teststring) Then
                returnval = teststring.Length
            End If
            ' Direct order, cutting from the beginning
            teststring = addeddirect.Substring(charscut)
            If IsPalyndrome(teststring & text) OrElse IsPalyndrome(text & teststring) AndAlso
                    returnval > teststring.Length Then
                returnval = teststring.Length
            End If
            ' reverse order, cutting from the end
            teststring = addedreverse.Substring(0, addedreverse.Length - charscut)
            If IsPalyndrome(teststring & text) OrElse IsPalyndrome(text & teststring) AndAlso
                    returnval > teststring.Length Then
                returnval = teststring.Length
            End If
            ' reverse order, cutting from the beginning
            teststring = addedreverse.Substring(charscut)
            If IsPalyndrome(teststring & text) OrElse IsPalyndrome(text & teststring) AndAlso
                    returnval > teststring.Length Then
                returnval = teststring.Length
            End If
            charscut += 1 ' 1 less character
        Loop
        Return (returnval)
    End Function
 
    Private Function IsPalyndrome(ByVal text As String) As Boolean
        Dim firsthalf As String = String.Empty
        Dim middle As String = String.Empty
        Dim lasthalf As String = String.Empty
 
        ' Determine if we have odd or even number of characters
        If (text.Length Mod 2) = 0 Then
            firsthalf = text.Substring(0, text.Length \ 2)
            lasthalf = text.Substring(text.Length \ 2)
        Else
            firsthalf = text.Substring(0, (text.Length - 1) \ 2)
            middle = text.Substring(firsthalf.Length, 1)
            lasthalf = text.Substring((firsthalf.Length + 1))
        End If
        Return New String(lasthalf.AsEnumerable.Reverse().ToArray()).Equals(firsthalf)
    End Function

Test results (slightly different due to the limitations described above):

Code:

AAABBBBCCCCC: 7

CCCCCBBBBAAA: 7

BBBBCCCCCAAA: 8

FASLLI: 5

ARBEN: 4

ARBENA: 5

ARBANA: 3

ALL: 1

ALLLL: 1

BAOUB: 4

ASDRFFF: 4

AAABBB: 3

ARBENARBEN: 9

ALLALL: 1

AAABBBBAAABBBBCCCCC: 9

Hope this helps...

Re: Palindrome Problem - Minimum number of characters to make a text palindrome

Quote:

Originally Posted by cicatrix

vb.net Code:

'
    Private Function CountCharsToPalyndrome(ByVal text As String) As Integer
        Dim addeddirect As String = text
        Dim addedreverse As String = New String(text.AsEnumerable.Reverse().ToArray())
        Dim returnval As Integer = addeddirect.Length
        ' Direct order, cutting from the end
        Dim teststring As String
        Dim charscut As Integer = 1
        Do While charscut < text.Length
            ' Direct order, cutting from the end
            teststring = addeddirect.Substring(0, addeddirect.Length - charscut)
            If IsPalyndrome(teststring & text) OrElse IsPalyndrome(text & teststring) Then
                returnval = teststring.Length
            End If
            ' Direct order, cutting from the beginning
            teststring = addeddirect.Substring(charscut)
            If IsPalyndrome(teststring & text) OrElse IsPalyndrome(text & teststring) AndAlso
                    returnval > teststring.Length Then
                returnval = teststring.Length
            End If
            ' reverse order, cutting from the end
            teststring = addedreverse.Substring(0, addedreverse.Length - charscut)
            If IsPalyndrome(teststring & text) OrElse IsPalyndrome(text & teststring) AndAlso
                    returnval > teststring.Length Then
                returnval = teststring.Length
            End If
            ' reverse order, cutting from the beginning
            teststring = addedreverse.Substring(charscut)
            If IsPalyndrome(teststring & text) OrElse IsPalyndrome(text & teststring) AndAlso
                    returnval > teststring.Length Then
                returnval = teststring.Length
            End If
            charscut += 1 ' 1 less character
        Loop
        Return (returnval)
    End Function
 
    Private Function IsPalyndrome(ByVal text As String) As Boolean
        Dim firsthalf As String = String.Empty
        Dim middle As String = String.Empty
        Dim lasthalf As String = String.Empty
 
        ' Determine if we have odd or even number of characters
        If (text.Length Mod 2) = 0 Then
            firsthalf = text.Substring(0, text.Length \ 2)
            lasthalf = text.Substring(text.Length \ 2)
        Else
            firsthalf = text.Substring(0, (text.Length - 1) \ 2)
            middle = text.Substring(firsthalf.Length, 1)
            lasthalf = text.Substring((firsthalf.Length + 1))
        End If
        Return New String(lasthalf.AsEnumerable.Reverse().ToArray()).Equals(firsthalf)
    End Function

Test results (slightly different due to the limitations described above):

Code:

AAABBBBCCCCC: 7

CCCCCBBBBAAA: 7

BBBBCCCCCAAA: 8

FASLLI: 5

ARBEN: 4

ARBENA: 5

ARBANA: 3

ALL: 1

ALLLL: 1

BAOUB: 4

ASDRFFF: 4

AAABBB: 3

ARBENARBEN: 9

ALLALL: 1

AAABBBBAAABBBBCCCCC: 9

Hope this helps...

I'll see if I can find how it works with the cases in which my output comes wrong, since yours comes right, so thank you very much, let's hope I can mix things in.

Wow, I actually mixed things, my code with yours. I check the output of my code and yours, and I print whomever has the smalles value, therefore when your code is mistaken and mine is right I print out my output and vice-versa. So for the texts I've studied, everything is fine.
I need to find more different examples and check them to find any possible cases where my code could be wrong since yours is very strict and I know when it is wrong, but still THANK YOU SO MUCH!