# Questions tagged [strings]

Questions about sequences of symbols, sets thereof and their properties as well as uses.

450 questions
Filter by
Sorted by
Tagged with
28 views

### An idempotent grammar for text decoding?

I'd like to create a function decode(x : string) such that decode(x : string) == decode(decode(x : string)). I believe I can ...
22 views

### Longest substring creating palindromic substring in other string

Given two strings $s, t$, I would liketo find a maximal subsequence of $t$ (denoted as $t'$), such that the concatenation of $t'$ with its reverse ($t'_R$), is a palindromic substring of $s$. I ...
20 views

### Finding matches between an input string and a fixed set of strings

I need to compare an input string to multiple strings which I'll refer to as fixed strings, and you can assume the latter won't change. Comparison disregards letters with special characters, only ...
21 views

### using TRIE for strings?

I saw the following question online: Init - Initlize data structure in O(1). Insert(s) - Add string s to your Data Structure in ...
5k views

### How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

I understand the textbook explanation of how to use dynamic programming to find the minimum edit distance between 2 strings but how do we get to pick the 2nd string? I don't think the entire ...
144 views

### Counting number of swaps to make two strings equal in linear time

The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant. ...
32 views

### Number of borders of all substrings in a string

Can you please help with solving the following problem. Given a string $s$, we need to find the number of borders of all its substrings. For a single string we can count all the borders in O(n) time ...
30 views

### Proving correctness for greedy algorithm in string removal problem

Problem Statement: You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points. For example, when ...
31 views

### High Level description of Turing Machines

How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
31 views

### Given a finite alphabet, how to generate all possible strings while excluding those that don't feature an element at least once?

Say you have the finite alphabet {a,b,c,d,e,f,g}. It's trivial to enumerate all strings of length <= 1000 over that set. But what would be an efficient way of specifying a subset of those strings ...
34 views

### Fast text comparison algorithm for long texts

I want to calculate a similarity ratio between two long texts (by "long", I imply something around 1000 characters or higher). For example, two texts with only one word changing should have ...
35 views

### Counting substrings of a string that do not contain a given string

Let's say we have a string $s[0..n-1]$ and a pattern $p[0..m-1]$ with $m < n$. I am looking for an $O(nm)$ solution to the following problem: find the number of substrings of $s$ not containing $p$ ...
37 views

### How can I prove that the empty string is the identity element with regards to the operation of concatenation?

Let $w$ be a string over an alphabet $\Sigma$. It is obvious that $w \circ \epsilon = \epsilon \circ w = w$. However I'm having a hard time coming up with a proof for that (which I assume should be ...
40 views

### Sum of squares of length of longest common prefix for all pairs in given strings

Given a list of unique strings, how can I find the sum of squares of longest common prefixes length for all pairs? I think a trie will be useful but I'm not sure how to calculate the final result. For ...
42 views

I am struggling to grasp the algorithm for building the KMP failure function. The bulk of what is making my understanding incomplete concerns the line ...
140 views

### What is the optimal solution for the following "Largest lexicographical string with <= K consecutive elements" problem? Why is my answer wrong?

This is a simple question I ran into in a remote interview: Given a collection of letters, permute them (or one of its subset) into a string such that: each letter can only be repeated for <= 11 ...
48 views

### Z-function and the minimum string period

Let $s$ be a string of length $n$. One of the classical solutions to the problem of finding the smallest period $p$ of $s$ (that is, smallest $p$ such that $s$ can be obtained as a concatenation of ...
19 views

### question about common prefix of Strings

we are given n Strings of total Length K and also we have m queries about these strings. each query, contains 2 index ( for example a , b ) and then we should calculate the length of longest common ...
77 views

### Remove a subsequence from a string and append it at the end

Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
30 views

26 views

### How to find the LCP of string pairs in a set

I have a set of $k$ strings of $n$ length each. I need an algorithmic strategy that finds the LCP (Longest Common Prefix) of each set's string pair. In addition, I need time complexity $O(k*n+a)$, ...
23 views

### Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)

If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because ...
47 views

### Longest palindrome after swapping operation

I know that Manacher's algorithm can be used to find the longest palindromic substring of a string in linear time. But I want to find the longest palindromic substring after swapping any two indices ...
108 views

### Can a Turing machine start on a blank?

Couldn't find a definitive answer anywhere so asking here. I have a Turing machine and the start state can go straight to the end state without passing through any of the other five states via Blank -...
188 views

### calculating the string similarity of an optimal alignment

description of the algorithms behavior I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
165 views

### Number of substrings possible with even characters

Consider a string 'ABBAA' Possible substrings with even number of characters are $4$ 'ABBA' : Count of 'A' is even and 'B' is even 'AA' : Count of 'A' is even and 'B' is even - ($0$) Similarly 'BB' ...
34 views

### Find the most frequent alphabet appearing in the given string. In case letter with same frequency, choose the one which comes first alphabetically

This is the desired result which I want:
72 views

### Las Vegas algorithm for finding 00000 in bit string

Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). ...
122 views

### Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$

Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$. This is exercise 6 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. ...
230 views