string,algorithm,probability,combinatorics,discrete-mathematics , How to find all strings that do not contain substring palindromes

## Question:

Tag: string,algorithm,probability,combinatorics,discrete-mathematics

Disclaimer: This is a problem lifted from HackerRank, but their editorial answer wasn't sufficient so I hoped to get better answers. If it's against any policy, please let me know and I'll take this down.

Problem: You are given two integers, N and M. Count the number of strings of length N under the alphabet set of size M that doesn't contain any palindromic string of the length greater than 1 as a consecutive substring.

N=2,M=2 -> 2 :: AA, AB, BA, BB

N=2,M=3 -> 6 :: AA, AB, AC, BA, BB, BC, CA, CB, CC

ABCDE counts as it does not contain any palindromic substrings.

ABCCC does not count as it does contain "CCC", a palindrome of length >1.

Editorial Here is the provided answer which I think is wrong:

For N>=3, there are (M−2) ways to choose any next symbol (after the first two) - basically it should not coincide with the previous and pred-previous symbols, that aren't equal.

``````If N=1, return M

If N=2, return M * (M-1)

If N>=3, return M * (M-1) * (M-2)^(N-2)
``````

counterexample: N=4, M=3, "ABCC"

My Solution Try When I was working on this problem, I tried to find all the strings that contained palindromic substrings and subtracting that from the total, M^N. I ran into a lot of problems with over counting. For example, "ABABA" has "ABA","BAB","ABA" of n=3, and "ABABA" of n=5.

Thanks for any help in elucidating this problem. I really hope for a good answer to figure this out!

Suppose you build up palindrome-free strings one letter at a time. For the first letter, you have M choices, and for the second, you have M-1, since you can't use the first letter. This much is obvious.

For every letter after the first two, you can't use the previous letter, and you can't use the letter before that, so that's two choices eliminated. What about the other letters? Well, if using one of those creates a palindrome, it would have to be a palindrome of length at least 4 - but if adding a letter creates a palindrome of length K+2 for K>=2, the string must already have had a palindrome of length K for the new palindrome to build off of. (For K<2, this is okay.) Since the string didn't have any palindromes of length >=2, we can conclude that adding any letter other than the previous two letters is fine.

Thus, we have M choices for the first letter, M-1 choices for the second, and M-2 for every letter after that.

# Related:

## How do I isolate the text between 2 delimiters on the left and 7 delimiters on the right in Python?

python,regex,string,split
I have a string: string = ""7807161604","Sat Jan 16 00:00:57 +0000 2010","Global focus begins tonight. Pretty interested to hear more about it.","Madison Alabama","al","17428434","81","51","Sun Nov 16 21:46:24 +0000 2008","243" I only want the text: "Global focus begins tonight. Pretty interested to hear more about it."" which is between the 2nd and...

## Does there exist an algorithm for iterating through all strings that conform to a particular regex?

c#,regex,algorithm
I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every...

## .cpp:23: error: cannot convert ‘std::string’ to ‘const char*’ for argument ‘1’ to ‘int atoi(const char*)’

c++,string
Here a basic code I'm trying to run But I'm having trouble with stoi (it's c++) I keep getting error: ‘stoi’ was not declared in this scope I tried atoi and strtol with this error .cpp:23: error: cannot convert ‘std::string’ to ‘const char*’ for argument ‘1’ to ‘int atoi(const char*)’...

## Split by a comma that is not inside parentheses, skipping anything inside them

java,regex,string,split
I know it might be another topic about regexes, but despite I searched it, I couldn't get the clear answer. So here is my problem- I have a string like this: {1,2,{3,{4},5},{5,6}} I'm removing the most outside parentheses (they are there from input, and I don't need them), so now...

## Remove Strings with same characters in a String Array

java,arrays,string
I'm facing a problem right now. In one of my program, I need to remove strings with same characters from an Array. For eg. suppose, I have 3 Arrays like, String[] name1 = {"amy", "jose", "jeremy", "alice", "patrick"}; String[] name2 = {"alan", "may", "jeremy", "helen", "alexi"}; String[] name3 = {"adel",...

## jQuery / Regex: How to compare string against several substrings

jquery,regex,string,substring,substr
I have a special validation need where I need to check if a string contains ANY out of several substrings like the following list: 12 23 34 45 56 67 78 89 90 01 I am new to jQuery and the only thing I could think of here is the...

## C++ & Qt: Random string from an array area

c++,arrays,string,qt,random
In my small Qt application, I want to pick a random string out of an array after I clicked on a button. I've read many threads but nothing works for me. So in my slot there's an array with several strings in it. I also implemented <string>, <time.h> and srand....

## A beginner questions about printf, java

java,string,printf
I'm learning Java by myself and through tutorials online. Just wondering in a printf statement, what does the different %s, %d, %15, %7, %12.2(and so on...) mean? Couldn't find any explanation anywhere online, so I'm turning to you. ...

## free causing different results from malloc

c,string,malloc,free
Below is a C program i have written to print different combination of characters in a string. This is not an efficient way as this algorithm creats a lot of extra strings. However my question is NOT about how to solve this problem more efficiently. The program works(inefficiently though) and...

## Reverse ^ operator for decryption

c,algorithm,security,math,encryption
I'm trying to reverse the following code in order to provide a function which takes the buffer and decrypts it. void crypt_buffer(unsigned char *buffer, size_t size, char *key) { size_t i; int j; j = 0; for(i = 0; i < size; i++) { if(j >= KEY_SIZE) j = 0;...

## Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off

algorithm
I attended a programming competition(it has ended now). I don't know why my solution is giving WA, I read the editorial, saw other people solution but unable to find a flaw in my solution. Obviously I am missing somewhere. Please help! Question Link My Solution My approach If the pattern...

## REGEX python find previous string

python,regex,string
I'm trying to find if the last word of the string is followed by a space or a special char, and if yes return the string without this space/special char For example : "do you love dogs ?" ==> return "do you love dogs" "i love my dog " (space...

## Translating a character array into a integer string in C++

c++,arrays,string
I was trying to achieve translating a character array into a integer string and corresponding character to their alphabetical order. For instance: A(a) = 0 , Z(z) = 25. string key_char = argv[1]; string key_num; for (int i = 0; i < key_char.length(); i++){ if (isalpha(key_char[i])){ if (islower(key_char[i])){ key_num[i] =...

## Regex pass dynamic values with boundry

c#,regex,string,boundary
I'm trying to pass a dynamic value at runtime with a boundary \b to a Regex function. My code is: static void Main(string[] args) { string sent = "Accelerometer, gyro, proximity, compass, barometer, gesture, heart rate"; string match = "gyro"; string bound = @"\b"; if (Regex.IsMatch(sent, @"\bgyro", RegexOptions.IgnoreCase)) { Console.WriteLine("match...

## C# IEnumerable and string[]

c#,arrays,string,split,ienumerable
i searched for a method to split strings and i found one. Now my problem is that i can´t use the method like it is described. Stackoverflow answer It is going to tell that i cannot implicitly convert type 'System.Collections.Generic.IEnumerable' to 'string[]'. The provided method is: public static class EnumerableEx...

## Identify that a string could be a datetime object

python,regex,algorithm,python-2.7,datetime
If I knew the format in which a string represents date-time information, then I can easily use datetime.datetime.strptime(s, fmt). However, without knowing the format of the string beforehand, would it be possible to determine whether a given string contains something that could be parsed as a datetime object with the...

## Find second to last word in multi-lined string array

java,string
I need to find second to last word in each line (they are divided by space) and find 3 most popular of them and find how many are there? Can you help me in any way? Input example: abcd i asd ffdds abcd ddd ? abcd ffdds asd ddd i...

## char* string substract function throws exception

c++,arrays,string,char
I'm working on my own string class called PString, I have this function that finds a specific character, like 6, and now I have this function called substr short fo substract, where I want to substract from 0 to [insertnumber]. the way I'm trying to call this is by doing...

## Characters and Strings in Swift

ios,string,swift,unicode,character
Reading the documentation and this answer, I see that I can initialize a Unicode character in either of the following ways: let narrowNonBreakingSpace: Character = "\u{202f}" let narrowNonBreakingSpace = "\u{202f}" As I understand, the second one would actually be a String. And unlike Java, both of them use double quotes...

## Create string without repeating the same element jn the string (Matlab)

string,matlab
I have a string "FDFACCFFFBDCGGHBBCFGE" . Could anyone help me to generate a new string with the same order but no element inside repeated twice. Thanks ! The expected output should be like this : "FDACBGHE"...

## Comparing cell contents against string in Excel

string,excel,if-statement,comparison
Following is my table file:*.css file:*.csS file:*.PDF file:*.PDF file:*.ppt file:*.xls file:*.xls file:*.doc file:*.doc file:*.CFM file:*.dot file:*.cfc file:*.CFM file:*.CFC file:*.cfc file:*.DOC I need a formula to populate the H column with True or False if it finds column G in column F (exact case). I used following but nothing seems to...

## Algorithmic big o order of growth code

algorithm,discrete-mathematics
I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me. What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int...

## C++11 Allocation Requirement on Strings

c++,string,c++11,memory,standards
I had heard that C++11 was going to require strings to be allocated in contiguous memory. I even thought I saw a stack overflow question on it, but I can't seem to find it. I know that in practice both gcc and Visual Studio do allocate strings contiguously, I'm just...

## How to match words in 2 list against another string of words without sub-string matching in Python?

I have 2 lists with keywords in them: slangNames = [Vikes, Demmies, D, MS Contin] riskNames = [enough, pop, final, stress, trade] i also have a dictionary called overallDict, that contains tweets. The key value pairs are {ID: Tweet text) For eg: {1:"Vikes is not enough for me", 2:"Demmies is...

## Android String if-statement

java,android,string
I have a if-statement in the start of my app if (ready.equals("yes")){ ... } and later on my code I have ready="yes"; but the if statement is never called, why? The ready="yes"; is called from a background thread, is that why? public void DownloadFromUrl(final String fileName) { //this is the...

## String manipulation with batch scripting

windows,string,batch-file,space
I need to save the variable in %%c temporarily which comes from a for loop. But when I try to do that, the content changes unexpectedly. Some space characters appear at the end of the string. The content of %%c is a.jpg by the way. echo %%ca REM prints a.jpga...

## Stopping condition on a recursive function - Haskell

So, I have this function which aims to align the text on the left without cutting words(only white spaces). However my problem is that I cannot find a stopping condition of the function and it goes infinitely. f n "" = "" --weak condition f n s = if n...

## String parsing with batch scripting

windows,string,parsing,batch-file,xml-parsing
I have a file called pictures.xml and it contains some pictures information like: <ResourcePicture Name="a.jpg"> <GeneratedPicture Name="b.jpg"/> <GeneratedPicture Name="c.jpg"/> </ResourcePicture> <ResourcePicture Name="z1.jpg"> <GeneratedPicture Name="z2.jpg"/> <GeneratedPicture Name="z3.jpg"/> <GeneratedPicture Name="z4.jpg"/> </ResourcePicture> What I want do do is to get each line in for loop and print the names of the pictures. Sample...

## Remove quotes to use result as dataset name

r,string
I've got a vector with a long list of dataset names. E.g myvector<-c('ds1','ds2,'ds3') I'd like to use the names ds1..ds3 to write a file, taking the file name from the vector. Like this: write.csv(dataset[i],file=paste(myvector[i],'.csv',sep='') with dataset being d1...ds3, but without quotes. How can I remove the quotes and refer to...

## Java, cut off array line before charactern nr. X

java,arrays,string,break
So i have massive(i mean massive) array. It has over 500000 lines. Each line starts with some bs that i don't need. What i need is EVERYTHING after 64th symbol(65th symbol is needed). It's the same for every line, but after 64th symbol each line lenght is different. How do...

## Giving a string variable as a filename in matlab

string,matlab,filenames
I am using the below mentioned code to get the file names of images according to their id's from images_1 text file as strings and use them to read the images from their directory image_count=1; for image_count=1:6 file=fopen('D:\Academics\New folder\CUB_200_2011\images_1.txt','r'); C = textscan(file, '%s'); original_image=imread('D:\Academics\New folder\CUB_200_2011\images\%s','C{1}{2*(image_count)}'); imshow(original_image) end I am able...

## Split by a word (case insensitive)

python,regex,string,split
If I want to take "hi, my name is foo bar" and split it on "foo", and have that split be case insensitive (split on any of "foO", "FOO", "Foo", etc), what should I do? Keep in mind that although I would like to have the split be case insensitive,...

## Display only values containing specific word in array

php,arrays,json,string,if-statement
Right now I am working on a search function for my json decoded results. The code that I got looks like this: <?php foreach(\$soeg_decoded as \$key => \$val){ \$value = \$val["Value"]; \$seotitle = \$val["SEOTitle"]; \$text = \$val["Text"]; echo '<tr><td>' . \$value . '</td><td>' . \$seotitle . '</td><td>' . \$text ....

## Program to reverse a string in C without declaring a char[]

c,string,pointers,char
I need to reverse a given string and display it without using the value At[index] notation , I tried the below program using pointers,but it does not print anything for the reverse string, Please help! int main() { char* name=malloc(256); printf("\nEnter string\n"); scanf("%s",name); printf("\nYou entered%s",name); int i,count; count=0; //find the...

## byte array to string and inverse : recoverded byte array is NOT match to original byte array in Java

java,string,bytearray
I converted a byte array to string as follow, in Java: String str_bytearray = new String(bytearray_original); and then, I recovered original byte array using string, as follow: byte[] bytearray_recovered = str_bytearray.getBytes(); but I wondered when I compared bytearray_original and bytearray_recovered. the result is as follow: [48, 89, 48, 19, 6,...

## 3 X 3 magic square recursively

c++,algorithm,math,recursion
I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

## SCALA: change the separator in Array

arrays,string,scala,delimiter
I have an Array like this. scala> var x=Array("a","x,y","b") x: Array[String] = Array(a, x,y, b) How do I change the separator comma in array to a :. And finally convert it to string like this. String = "a:x,y:b" My aim is to change the comma(separators only) to other separator(say,:), so...

## How To Check Value Of String

javascript,css,string,numeric
<span id='amount'>0.00000000</span> <a class='button-withdraw' id='tombolco' href='#'>Checkout</a> <script> var amount = document.getElementById("amount").innerHTML; if (amount >= 0.001) { document.GetElementById("tombolco").style = "display:block"; } else { document.GetElementById("tombolco").style = "display:none"; } </script> Why my code doesn't work? What's wrong with it and how to solve it?...

## Understanding Big-Ω (Big-Omega) notation

algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

## Regex to remove `.` from a sub-string enclosed in square brackets

c#,.net,regex,string,replace
I have this regex in C#: \[.+?\] This regex extracts the sub-strings enclosed between square brackets. But before doing that I want to remove . inside these sub-strings. For example, the string hello,[how are yo.u?]There are [300.2] billion stars in [Milkyw.?ay]. should become hello,[how are you?]There are [3002] billion stars...

## How can I convert an int to a string in C++11 without using to_string or stoi?

c++,string,c++11,gcc
I know it sounds stupid, but I'm using MinGW32 on Windows7, and "to_string was not declared in this scope." It's an actual GCC Bug, and I've followed these instructions and they did not work. So, how can I convert an int to a string in C++11 without using to_string or...

## What is the usage of adding an empty string in a javascript statement

javascript,string,concatenation
I see an empty string ('' or "") used in many JavaScript statements but not sure what does it stand for. e.g. var field = current.condition_field + ''; Can someone please clarify?...

## Matching string inside file and returning result

regex,string,bash,shell,grep
I've got a few peculiar issues with trying to search for a string inside of a .db file. The way I tried was by using grep, which does apparently find the string(s), although this is the output: \$ grep "ext" *.db Binary file enormous.db matches There are a couple problems...

## Disconnect all vertices in a graph - Algorithm

algorithm,graph
I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...

## Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554

c++,algorithm,parallel-processing,c++14
Proposal N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum, e.g.: template< class ExecutionPolicy, class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan( ExecutionPolicy &&exec, InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); With the explanation Effects: For each...

## Memory consumption when chaining string methods

c#,string,immutability,method-chaining
I know that string in C# is an immutable type. Is it true that when you chain string functions, every function instantiates a new string? If it is true, what is the best practice to do too many manipulations on a string using chaining methods?...

## What is this algorithm mapping coordinates to numbers called?

algorithm,coordinates,coordinate-systems,coordinate
I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types The problem was that I wanted...

## Swift: String contains Character?

string,swift,character
How do I check if a String includes a specific Character? For example: if !emailString.hasCharacter("@") { println("Email must contain at sign.") } ...

## I need to make sure that only certain characters are in a list?

python,regex,string,list,python-2.7
I have this to get input and put it in a list: def start(): move_order=[raw_input("Enter your moves: ").split()] And I only want the characters A, D, S, C, H (it's for a game >_>) to be allowed. I've tried using the regular expressions stuff: if re.match('[ADSCH]+', [move_order]) is False: print...

## Dynamic programming: how to design algorithm for when there are two factors to consider?

algorithm,optimization,dynamic-programming,frequency
I have the following problem and I only have a slight idea about it: Consider a tape storage problem. Given n files of length l1,...,ln and frequencies with which they are accessed f1,...,fn, where sum of all frequencies is 1 and 0<fi<1. "Optimal" means to minimize the average retrieval time...