Найдите длину самой длинной подстроки с неповторяющимися символами

С синтаксисом POSIX shи одним вызовом утилиты sed,вы можете сделать что-то вроде:

<input sed '
  # clean-up hold space
  x;s/.*//;x

  # insert a running ">" cursor
  s/^/>/
  :start
  />$/! {
    # pull the next character
    s/>\(.\)/\1>/

    # if what is left of > contains a duplicated character
    /\(.\).*\1.*>/ {
      # remove first char
      s/^.//
      b start
    }

    # does not contain a duplicated char. Is it longer than
    # the currently selected one?

    H; # append to hold space
    g;s/\n/>/;s/[^>]/./g
    # now the pattern space contains...>....>... and we compare
    # the number of.s in the first two sections

    /^\([^>]*\)>\1[^>]/ {
      # it is longer, store in hold space
      g
      s/.*\n//;s/>.*//
      x
      s/.*\n//
      b start
    }

    # it is not longer
    g
    s/\n.*//;x;s/.*\n//
    b start
  }
  g

  # count the number of characters
  s/./o/g
  s/^/:|/
  :1
  s/|o\{10\}/x|/
  t 1

  s/$/9876543210/
  s/\(.*:\)\(x*\)|.\{9\}\(.\).*/\3\1|\2/
  y/x/o/
  /o/b1
  s/:.*//
  G
  s/\(.*\)\n\(.*\)/"\2" (\1)/
'

Это дает самую длинную последовательность символов без повторяющихся символов для каждой строки ввода и предполагает, что ввод не содержит >символов.

Использование операторов раскрытия параметров POSIX sh, один вызов утилиты printfи несколько утилит [:

string=abcbdbdsdfng

cur= n=0 longest=
while [ -n "$string" ]; do
  c=${string%"${string#?}"}

  new_cur=${cur#*"$c"}
  if [ "$new_cur" = "$cur" ]; then
    cur=$cur$c
    string=${string#?}
    l=${#cur}
    if [ "$l" -gt "$n" ]; then
      n=$l longest=$cur
    fi
  else
    cur=$new_cur
  fi
done
printf '"%s" (%d)\n' "$longest" "$n"

Использование синтаксиса POSIX shи один вызов утилиты awk:

<input awk '
  {
    cur = longest = ""
    n = l = 0
    while ($0 != "") {
      c = substr($0, 1, 1)
      if (i = index(cur, c)) {
        cur = substr(cur, i+1)
        l -= i
      }
      $0 = substr($0, 2)
      cur = cur c
      if (++l > n) {
        n = l
        longest = cur
      }
    }
    printf "\"%s\" (%d)\n", longest, n
  }'

$ bash testing.sh abcbdbdsdfng
    5 sdfng

$ cat testing.sh
    #!/bin/bash
    echo "${1}" | awk '
    {
            res=$1;
            for(i=2;i<=NF;i++)
            {
                    idx=index(res,$i);
                    res=res""$i;
                    if(idx>0)
                    {
                            val=substr(res,idx+1,length(res));
                            res=val;
                    }
                    Arr[length(res)]=res;
                    max=(length(res)>max)?length(res):max;
            }
            print max,Arr[max];
    }' FS=""

Еще один, также использующий awk, так как это была действительно интересная задача.

awk -v s='abcbdbdsdfng' '
    BEGIN {
        m=""                                  # maximum length string
        while(s>"") {
            n=""                              # new string we are testing
            for (i=1; i<=length(s); i++) {
                c=substr(s,i,1)
                if (h[c]++) break             # break out if we have seen this char
                n=n c                         # add to the string and loop around
            }
                                              # end of source, or hit a duplicate
            if (length(m) < i-1) m=n          # save this string if it is longer
            split("", h)                      # erase the hash
            s=substr(s,2)                     # discard the front the source and loop
        }
        printf "%s (%d)\n", m, length(m)
        exit
    }
'

Версия Python:

def longest(r): # Find longest different substring in 'r'
    for i in range(1, len(r)):
        if  r[i] in r[:i]:
            return r[:i]
    return r[:(i + 1)]

s = 'abcbdbdsdfng'

print(max(len(longest(s[i:])) for i in range(len(s)-1)))

Поиск самой длинной подстроки без повторяющихся символов (LSRC )в оболочке оказывается достаточно просто (да, переносимыйsh)язык (не быстрый, обработка текста в оболочке обычно медленная):

#!/bin/sh

str=$1  longest='' teststr=''

while [ "${str}" ]; do
    c=${str%"${str#?}"}              # extract one char to test it.

    str=${str#?}                     # remove the character from str.

    teststr=${teststr#*"$c"}$c       # Build teststr by appending $c
                                     # remove leading repeated char.

              l1=${#longest}         # length of longest found
              l2=${#teststr}         # length of tested string

    if     [ "$l1" -lt "$l2" ]       # if tested is longer than longest
    then   longest=$teststr          # store it in longest.
    fi

done

echo "$longest ${#longest}";         # print longest found and length.

Описание Существует два общих алгоритма для поиска самой длинной подстроки без повторяющихся символов

Второй подход, также называемый «скользящим окном», работает по:

1. Начните со всей входной строки вstr(сделайте teststrи longestпустыми ). Затем в цикле:
2. Извлеките один символ(c)из начала str.
3. Проверить, повторяется ли cвнутри teststr.
4. Если cповторяется, продолжайте удалять символы перед teststr.
5. Если cне повторяется внутри teststr:, добавьте cк teststr.
6. Проверьте, длиннее ли teststr, чем longest. Если это так, сохраните эту строку в longest.
7. Как только в strне останется символов, цикл завершится.

Шаги 3,4 и 5 можно сократить до одной строковой операции :«удалить все до c(, если оно существует ), и добавить c». Если нет повторения currChar, ничего не удаляется, если есть повторение, все символы до повторения удаляются за один шаг. Это делается в оболочке с помощью ${frontstr#*"$c"}$c, всего одной переменной расширения.

Более простое решение для awk:

awk '
     {  teststr=""; longest=""; str=$0

        while (str>"")                        # until we test all chars.
        {
            char=substr(str, 1, 1)           # extract first character.
            str=substr(str, 2)                # delete first character.

            sub("^.*"char,"",teststr)         # delete up to a repeated char (if any).
            teststr=teststr char              # Append the tested char.

            if(length(teststr)>length(longest)){longest=teststr}
        }

        print(longest,length(longest))

     }
    ' file

int lengthOfLongestSubstring(char *s) {
  int count = 1;
  int max_count = 1;
  int j_start = 0;

  if (!s[0])
    return 0;
  else if (!s[1])
    return max_count;

  for (int i = 1; s[i]; i++) {
    for (int j = j_start; j < i; j++) {
      if (s[i] != s[j])
        count++;
      else
        j_start = j + 1;
    }
    if (max_count < count)
      max_count = count;
    count = 1;
  }
  return max_count;
}