(C卷,100分)- 求满足条件的最长子串的长度（Java & JS & Python & C）

题目描述

给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度，字符串本身是其最长的子串，子串要求：

1、 只包含1个字母(a~z, A~Z)，其余必须是数字；

2、 字母可以在子串中的任意位置；

如果找不到满足要求的子串，如全是字母或全是数字，则返回-1。

输入描述

字符串(只包含字母和数字)

输出描述

子串的长度

用例

题目解析

此题可以用滑动窗口求解。

滑动窗口的左指针开始指向索引0，右指针也是从索引0开始不断向右移动，当右指针遇到字母时，则滑动窗口内部含字母量+1。

当滑动窗口内部含有两个字母时，存在如下情况：

此时，我们需要移动left指针来达到减少一个字母的目的，但是单纯的left++就能减少一个字母吗？

我们可以看看上面第三个圈的情况，当left指针指向的是数字，如果left++，则滑动窗口内的字母并不会减少。

因此，我们需要判断left指针当前指向的元素是否为字母，如果为字母，则left++才能起到减少一个字母的作用，否则不能。

那么当left指针当前指向的是数字，则left指针应该如何跳转呢？

如上面第三个圈内所示，貌似是直接 left = right，但是真是这样吗？请看下面例子

从上面例子可以看出，当left指针指向数字，但是滑动窗口内已经有两个字母时，left应该移动到第一个字母的后面一个位置target。target位置只有两种数据：字母或数字，如果是字母则target位置就是滑动窗口内第二字母的位置，如果是数字，则避免了长度损失。 

而为了能够准确跳转到滑动窗口内第一个字母后面一个位置，我们在right指针扫描过程中，就需要记录字母所在的索引。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

/* 滑动窗口 */
function getResult(s) {
  let maxLen = -1;

  let l = 0,
    r = 0;

  let hasLetter = false;

  const letterIdx = [];

  while (r < s.length) {
    if (isLetter(s[r])) {
      hasLetter = true;
      letterIdx.push(r);

      if (letterIdx.length > 1) {
        l = letterIdx.shift() + 1;
      }

      if (r == l) {
        r++;
        continue;
      }
    }

    maxLen = Math.max(maxLen, r - l + 1);
    r++;
  }

  if (!hasLetter) return -1;
  return maxLen;
}

function isLetter(c) {
  return (c >= "a" && c <= "z") || (c >= "A" && c <= "Z");
}

Java算法源码

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.next()));
  }

  private static int getResult(String str) {
    int maxLen = -1;
    boolean hasLetter = false;

    int l = 0, r = 0;
    LinkedList<Integer> letterIdx = new LinkedList<>();

    while (r < str.length()) {
      char c = str.charAt(r);

      if (isLetter(c)) {
        hasLetter = true;
        letterIdx.add(r);

        if (letterIdx.size() > 1) {
          l = letterIdx.removeFirst() + 1;
        }

        if (r == l) {
          r++;
          continue;
        }
      }

      maxLen = Math.max(maxLen, r - l + 1);
      r++;
    }

    if (!hasLetter) return -1;
    return maxLen;
  }

  public static boolean isLetter(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
  }
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult():
    maxLen = -1

    l = 0
    r = 0
    letterIdx = []
    hasLetter = False

    while r < len(s):
        if s[r].isalpha():
            hasLetter = True
            letterIdx.append(r)

            if len(letterIdx) > 1:
                l = letterIdx.pop(0) + 1

            if r == l:
                r += 1
                continue

        maxLen = max(maxLen, r - l + 1)
        r += 1

    if not hasLetter:
        return -1
    return maxLen


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a,b) ((a) > (b) ? (a) : (b))

typedef struct ListNode{
    int ele;
    struct ListNode* next;
} ListNode;

typedef struct {
    int size;
    ListNode* head;
    ListNode* tail;
} LinkedList;

LinkedList* new_LinkedList();
void addLast_LinkedList(LinkedList* link, int ele);
int removeFirst_LinkedList(LinkedList* link);

int main() {
    char s[100000];
    gets(s);

    int maxLen = -1;
    int hasLetter = 0;

    int l = 0;
    int r = 0;

    LinkedList* letterIdx = new_LinkedList();

    int len = strlen(s);
    while(r < len) {
        char c = s[r];

        if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
            hasLetter = 1;
            addLast_LinkedList(letterIdx, r);

            if(letterIdx->size > 1) {
                l = removeFirst_LinkedList(letterIdx) + 1;
            }

            if(r == l) {
                r++;
                continue;
            }
        }

        maxLen = MAX(maxLen, r - l + 1);
        r++;
    }

    if(!hasLetter) {
        puts("-1");
    } else {
        printf("%dn", maxLen);
    }


    return 0;
}

LinkedList* new_LinkedList() {
    LinkedList* link = (LinkedList*) malloc(sizeof(LinkedList));

    link->size = 0;
    link->head = NULL;
    link->tail = NULL;

    return link;
}

void addLast_LinkedList(LinkedList* link, int ele) {
    ListNode* node = (ListNode*) malloc(sizeof(ListNode));

    node->ele = ele;
    node->next = NULL;

    if(link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        link->tail = node;
    }

    link->size++;
}

int removeFirst_LinkedList(LinkedList* link) {
    if(link->size == 0) exit(-1);

    ListNode* removed = link->head;

    if(link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
    }

    link->size--;

    int res = removed->ele;

    free(removed);

    return res;
}