string handling

[leo2008]

I am trying to resolve the below string manipulation.
But code doesn't work as expected. Need help with some inputs.

Input

First line of input contains string M, consisting of lowercase English letters. Second line of input contains integer N, consisting of characters to be removed.

Output

Print 1 if string is k-drome, 0 otherwise. Here the constraint is 1 <= length of M <= 100

//function to resolve the string
//function to resolve the string
bool isKdrom(char * M, int N, int k)
{
	while (N >=1 && M[0] == M[N-1])
	{
		M++; N-=2;
	}

	if (N <= 1) return true;

	if (k > 0)
		return isKdrom(M+ 1, N-1, k-1) || isKdrom(M, N-1, k-1);

	return false;
}

[jonnin]

The bugs are rather subtle. You changed M and N so your recursive calls AFTER DOING THAT are nonsense, and bungle your result. You also were returning true when N was too small, but on the recursive calls, that is not correct as those calls imply a state of false coming in, so unless it goes into the loop, it needs to return false on those.
With some modifications to account for that problem:

bool isKdrom(char * M, int N, int k)
{
	char* mcpy{M};
	int   ncpy{N};
	if(N < 2) return false;
	bool result{true};
	while (N >=1 )
	{		
		result &= M[0] == M[N-1];	
		M++; N-=2;
	}	
	M = mcpy;
	N = ncpy;
	
	if (result) return true;

	if (k > 0)
		return isKdrom(M+ 1, N-1, k-1) || isKdrom(M, N-1, k-1);

	return false;
}

int main()
{
	cout << std::boolalpha;
  char c[] = "12321";
  char c2[] = "1221";
  char c3[] = "123";
  char c4[] = "123219";
  cout << isKdrom(c,strlen(c),  2)<<endl;
  cout << isKdrom(c2,strlen(c2),2)<<endl;
  cout << isKdrom(c3,strlen(c3),2)<<endl;
  cout << isKdrom(c4,strlen(c4),2)<<endl;
 
}

this may not be 100% correct even now. But its closer. It will NOT return true for initial strings of length 1, which is not technically correct ("x" is a trivial drome). To fix that you would need to tie result bool back into the recursion so it is aware of 'first call exception' somehow. Another sneaky way to do that is to add a default parameter to the end. The recursive calls can put a value there, the user will only have the default. The default will then indicate first time exception:
bool isKdrom(char * M, int N, int k, bool first = true)
{
if(first && N == 1) return true;
blah, blah
return isKdrom(M+ 1, N-1, k-1, false) || ...
}
main()
isKdrom(c,strlen(c),2); //leave last parameter empty here!

I fixed it with the 'bandaid' approach so you can SEE what was wrong with it clearly.
the right thing to do is a rewrite that cleans this mess up, with the new ideas in place and such.

[lastchance]

#include <iostream>
#include <string>
using namespace std;


bool isPalindrome( const string &str )
{
   for ( int p = 0, q = str.size() - 1; p < q; p++, q-- )
   {
      if ( str[p] != str[q] ) return false;
   }
   return true;
}


bool iskdrome( const string &str, int k )
{
   if ( k == 0 ) return isPalindrome( str );
   if ( isPalindrome( str ) ) return true;
   if ( iskdrome( str.substr( 1 ), k - 1 ) || iskdrome( str.substr( 0, str.size() - 1 ), k - 1 ) ) return true;
   for ( int i = 1; i < str.size() - 1; i++ )
   {
      if ( iskdrome( str.substr( 0, i ) + str.substr( i + 1 ), k - 1 ) ) return true;
   }
   return false;
}


int main()
{
   int k = 2;
   string tests[] = { "abcbca", "abcdef", "a", "aabb", "aaabbb" };
   for ( string s : tests ) cout << s << ": " << boolalpha << iskdrome( s, k ) << '\n';
}

abcbca: true
abcdef: false
a: true
aabb: true
aaabbb: false

[leo2008]

I am trying to use the same function signature bool isKdrom(char * M, int N, int k) here. M is of type char * and N, k are type of int. The function must return an integer type value, as it accepts the above parameters in the fn signature.

[Enoizat]

for ( int p = 0, q = str.size() - 1; p < q; p++, q-- )

Hi, lastchance.
Do we need to check the entire word? Wouldn’t it be enough to check if its first half matches its second half (going backward)?

[lastchance]

Hello @Enoizat,
It checks one character at a time working from both ends, exiting early (without checking any more) if there is a mismatch.

What would you like it to do?

[Enoizat]

The same, but only for half word.
I mean, e.g 'racecar':

-> -> ->  |  <-  <-  <-
r  a  c   e   c   a   r

Wouldn’t the first half of a palindrome being the same of its second half in reverse order? So, what about checking only half of the word?

[Ganado]

The looping condition is p < q, where p is increasing and q is decreasing, so this will end at half way at most.

[Enoizat]

Right!
I don’t know what I was thinking – I was probably already sleeping and I didn’t realize it.
Sorry, everyone. Have a nice day.