string,algorithm,palindrome , Given length L find the shortest string formed only of as & bs >= L such that adding some character (Either a or b) doesn't produce a new palindrome


Given length L find the shortest string formed only of as & bs >= L such that adding some character (Either a or b) doesn't produce a new palindrome

Question:

Tag: string,algorithm,palindrome

Given length L find the shortest string >= L formed only of as & bs such that adding some character (Either a or b) doesn't produce a new palindrome substring (never seen before palindrome)

For example for L = 1 there is the string aabbaba, adding "a" to it to result in aabbabaa will only produce the palindromes "a" and "aa" which were seen before at the 1st and 2nd character positions, but for example the string aabab doesn't work because adding "b" or "a" will produce the new palindromes "bb" and "ababa" respectively

I'm not even sure aabbaba is the optimal solution for L = 1. Any ideas on an algorithm to solve this fast?


Answer:

Here are my results so far:

All futher L can be solved just by prefixing an additional a to the starting string.


Related:


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...

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 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?...

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 ....

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...

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.") } ...

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...

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...

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...

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...

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...

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...

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...

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?...

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...

.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*)’...

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...

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


python,regex,string,loops,twitter
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...

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...

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;...

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...

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...

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...

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...

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...

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...

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...

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...

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"...

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....

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...

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...

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...

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...

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",...

Stopping condition on a recursive function - Haskell


string,function,haskell,if-statement,recursion
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...

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...

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...

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...

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...

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...

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,...

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...

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,...

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. ...

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...

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...

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] =...

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...