Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common character.

Examples:

  1. y d c b f

Answer = $3$ (common character is 'c')

  1. n n n n n n n n n

Answer = $1$ (common character is 'n')

  1. y e y d y e y

Answer = $2$ (common character is 'y')

The only solution I have thought of till now goes like this:

Find all sub-strings of length $x$ from $1$ through $n-1$ (where $n$ is the length of the given string). Compare the sub-string for common characters (and store which characters are common). As soon as I come across a pair of the sub-string of length $x$ which doesn't have any common characters I move to the next value of $x$. If no such $x$ is found, return $n$.

Is a more efficient solution possible?

  • 1
    Do you want your sub-strings to all have the same common character, or do only all pairs of sub-strings need to have some common character, possibly different for different pairs? – Discrete lizard Jan 23 at 11:46
  • All substrings need to have the same common character. I have explained in a little more detail in gnasher729's answer below. – John Doe Jan 23 at 12:02
  • You should edit your answer to remove ambiguity, as well. Perhaps include another example for which the result would differ. – Discrete lizard Jan 23 at 12:17
  • Hint: Suppose the largest gap between two copies of letter X is 42. Then every substring of length at least _____ must have at least one copy of ______. – j_random_hacker Jan 23 at 15:05
  • 2
    Please do not vandalise your posts. Once you have submitted a post, you have licensed the content to the Computer Science community at large (under the CC BY-SA license). By SE policy, any vandalism will be reverted. – CalvT Jan 23 at 16:20
up vote 0 down vote accepted

An equivalent formulation of your problem is:

Given a string $S$ of length $n$, what is the minimal $k$ such that there exists an character $s\in S$ such that for all $i\in\{1,\ldots,n\}$, there exists a $j$ s.t. $|i-j|\leq k$ and $S[j]=s$. Report $k+1$.

Your approach seems to take $O(n^4)$ time in the worst case. If you try to see if the above formulation holds for all characters $s\in S$, you should be able to do it in $O(n)$:

Do a single linear scan trough $S$, while maintaining the last index you've seen each of the characters present in $S$ and the maximum gap size for each of those characters. After that, pick the character $s\in S$ with the smallest maximum gap size, this size is the value $k$. (Improved to a single pass thanks to @j_random_hacker's remark)

So, you can solve this problem in $O(n)$ time, which is a lot better than your initial approach. This approach is even asymptotically optimal, as we have to at least scan the entire string in the worst case, so we require at least $\Omega(n)$ time.

  • @JohnDoe If $|D|=26$ or even $|D|=C$ for any fixed constant $C$, i.e. we only consider strings over a fixed alphabet, then this approach would indeed be linear. In this case, the solution is even asymptotically optimal: we would at least have to scan the entire string once, so we need to spend $\Omega(n)$ time in any case. – Discrete lizard Jan 23 at 13:38
  • 1
    You can do just one scan, but instead of maintaining the last-seen position of a chosen single character, maintain the last-seen positions of every character in a table. At each position in $S$ you only need to check and update this table for the character at the current position. – j_random_hacker Jan 23 at 16:30
  • @Discretelizard I think we have to initialize the initial gap position for each character as half the string size for the case when there are no duplicates. – noman pouigt Jan 24 at 19:06
  • @nomanpouigt The initial gap size should be large enough, yes. Half the string size seems to be enough.The position shouldn't be initialized. – Discrete lizard Jan 24 at 19:32

You assume that all substrings would need to have the same common character, but that is not the case.

Take a string that repeats the following:

abcdefghijxy0123456789xzabcdefghijyz0123456789xyabcdefghijxz0123456789yz

Every substring of length 12 contains two of x, y and z, so any two substrings of length 12 have a common character. But there are substrings of length 22 containing no x, substrings of length 22 containing no y, and substrings of length 22 containing no z.

You find the minimum length for a globally common character easily in O(n) by keeping track of the length of gaps for each character, and picking the shortest maximum gap. Here's how you do it:

for each character c
    c.lastfound = 0
    c.largestgap = 0

for 1 ≤ i ≤ length (string)
    let c = character #i of the string
    c.largestgap = max (c.largestgap, i - c.lastfound)
    c.lastfound = i

let minlength = length (string)
for each character c
    c.largestgap = max (c.largestgap, length (string) + 1 - c.lastfound)
    minlength = min (minlength, c.largestgap)

Any substring of length minlength contains the character(s) c where c.largestgap = minlength, and any two such substrings have those characters in common. On the other hand, if we take len < minlength, then for every character c we have c.largestgap > len. And when c.largestgap was set to that value > len, the preceeding c.largestgap - 1 characters in the string didn't contain c, so there is a substring of length len not containing c.

Runtime is O (max (length (string), number of characters).

The original problem (where you asked for a common character, not for all substrings having the same common character), is a lot harder. Finding the length needed for the same common character is very easy and gives an upper bound.

  • I think your interpretation of pairwise common characters need not necessarily be what the question asker had in mind. But it is a bit ambiguous: this requires clarification. – Discrete lizard Jan 23 at 11:45
  • That’s what you meant, but not what you asked. What you asked is much more difficult, what you meant is trivial. – gnasher729 Jan 23 at 12:29
  • @gnasher729 I disagree. Whether the scope of 'common characters' is over pairs or over all strings is ambiguous. I read one interpretation, you the other. Perhaps you can create a new question with the other interpretation and self-answer. – Discrete lizard Jan 23 at 12:39
  • @Discretelizard: If you haven't noticed, one problem is trivial, and one is bloody hard. And one of the most important thing for anyone wanting an answer is to ask clear and unambiguous questions. – gnasher729 Jan 23 at 22:22
  • What does the difficulty have to do with the interpretation of the question? From the askers perspective, the difficulty of a problem is often unknown. And yes, asking clear questions is important, but so is asking for clarification if the problem is unclear. (which we both failed to do due to our hasty assumptions) – Discrete lizard Jan 23 at 22:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.