leetcode系列(双语)003——GO无重复字符的最长子串

文章目录

  • 003、Longest Substring Without Repeating Characters
  • 个人解题
  • 官方解题
  • 扩展

003、Longest Substring Without Repeating Characters

无重复字符的最长子串

Given a string s, find the length of the longest substring without repeating characters.

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

Example :
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

示例:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

个人解题

func lengthOfLongestSubstring(s string) int {
	m := make(map[uint8]int)
	//记录当前字符的长度
	strLen := 0
	//记录最大的字符的长度
	maxStrLen := 0
	//计算字符的长度的开始下标
	start := 0

	for i := 0; i < len(s); i++ {
		//查询判断m是否存在字符
		temp := m[s[i]]
		if temp == 0 {
			//不存在,保存记录
			m[s[i]] = 1
			//当前长度+1
			strLen++
		} else {
			//存在重复字符串
			//判断当前长度是否超过最大长度
			if strLen > maxStrLen {
				maxStrLen = strLen
			}
			//重置
			strLen = 0
			if start < len(s) {
				i = start
				m = make(map[uint8]int)
			} else {
				break
			}
			start++
		}
	}
	//判断当前长度是否超过最大长度
	if strLen > maxStrLen {
		maxStrLen = strLen
	}
	return maxStrLen
}

在这里插入图片描述

官方解题

func lengthOfLongestSubstring(s string) int {
    // 哈希集合,记录每个字符是否出现过
    m := map[byte]int{}
    n := len(s)
    // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
    rk, ans := -1, 0
    for i := 0; i < n; i++ {
        if i != 0 {
            // 左指针向右移动一格,移除一个字符
            delete(m, s[i-1])
        }
        for rk + 1 < n && m[s[rk+1]] == 0 {
            // 不断地移动右指针
            m[s[rk+1]]++
            rk++
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1)
    }
    return ans
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

扩展

Given a string, print the longest substring without repeating characters in Golang. For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA”.

Examples:

Input : GEEKSFORGEEKS
Output :
Substring: EKSFORG
Length: 7

Input : ABDEFGABEF
Output :
Substring: BDEFGA
Length: 6
The idea is to traverse the string and for each already visited character store its last occurrence in an array pos of integers(we will update the indexes in the array based on the ASCII values of the characters of the string). The variable st stores starting point of current substring, maxlen stores length of maximum length substring, and start stores starting index of maximum length substring.

While traversing the string, check whether the current character is already present in the string by checking out the array pos. If it is not present, then store the current character’s index in the array with value as the current index. If it is already present in the array, this means the current character could repeat in the current substring. For this, check if the previous occurrence of character is before or after the starting point st of the current substring. If it is before st, then only update the value in array. If it is after st, then find the length of current substring currlen as i-st, where i is current index.

Compare currlen with maxlen. If maxlen is less than currlen, then update maxlen as currlen and start as st. After complete traversal of string, the required longest substring without repeating characters is from s[start] to s[start+maxlen-1].

// Golang program to find the length of the
// longest substring without repeating
// characters

package main

import “fmt”

func longest_substring(s string, n int) string {

var i int
  
// starting point of 
// current substring. 
st := 0     
  
// length of current substring.   
currlen := 0  
  
// maximum length substring  
// without repeating  characters 
maxlen := 0   

// starting index of  
// maximum length substring. 
start := 0 

// this array works as the hash table 
// -1 indicates that element is not 
// present before else any value  
// indicates its previous index 
pos := make([]int, 125) 

for i = 0; i < 125; i++ { 

    pos[i] = -1 
} 

// storing the index 
// of first character 
pos[s[0]] = 0 

for i = 1; i < n; i++ { 

    // If this character is not present in array, 
    // then this is first occurrence of this 
    // character, store this in array. 
    if pos[s[i]] == -1 { 
        pos[s[i]] = i 
    } else { 
      
        // If this character is present in hash then 
        // this character has previous occurrence, 
        // check if that occurrence is before or after 
        // starting point of current substring. 
        if pos[s[i]] >= st { 

            // find length of current substring and 
            // update maxlen and start accordingly. 
            currlen = i - st 
            if maxlen < currlen { 

                maxlen = currlen 
                start = st 
            } 
            // Next substring will start after the last 
            // occurrence of current character to avoid 
            // its repetition. 

            st = pos[s[i]] + 1 

        } 
        // Update last occurrence of 
        // current character. 
        pos[s[i]] = i 
    } 

} 
// Compare length of last substring  
// with maxlen and update maxlen  
// and start accordingly. 
if maxlen < i-st { 

    maxlen = i - st 
    start = st 
} 
  
// the required string 
ans := ""

// extracting the string from  
// [start] to [start+maxlen] 
for i = start; i < start+maxlen; i++ { 
    ans += string(s[i]) 
} 

return ans 

}

func main() {

var s string = "GEEKSFORGEEKS"
var n int = len(s) 

// calling the function to  
// get the required answer. 
var newString = longest_substring(s, n) 
  
// finding the length of the string 
var length int = len(newString) 

fmt.Println("Longest substring is: ", newString) 
fmt.Println("Length of the string: ", length) 

}
Output:

Longest substring is: EKSFORG
Length of the string: 7
Note: Instead of using the array, we can also use a map of string to int.

Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, GeeksforGeeks Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out - check it out now!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/162920.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

深信服AC密码认证(外部认证:LDAP认证)

拓扑图 搭建好自己AD域服务器&#xff0c;我搭建的服务器域名叫做liyanlongyu.com&#xff0c;如何搭建这里我就不做演示了 一.在AC中添加自己AD域服务器 二.添加LDAP认证策略 验证&#xff1a; 未认证发现&#xff0c;无法上网 点击网页&#xff0c;弹出认证页面 认证后&…

硬件工程师基础能力课

第一课时--基本定理、电阻、电容等 首先了解下面几个概念&#xff0c;基尔霍夫定理&#xff1a;KCL & KVL&#xff0c;叠加定理&#xff0c;戴维南定理&#xff08;电压源等效&#xff09;和诺顿定理&#xff08;电流源等效&#xff09;、奈奎斯特采样定理。 上面说的这些东…

微机原理_12

一、单项选择题(本大题共15小题,每小题3分&#xff0c;共45分。在每小题给出的四个备选项中&#xff0c;选出一个正确的答案。〕 十进制正数56的 8位二进制补码是()。 A. 00011001 B. 10100110 C. 10011001 D. 00100110 若栈顶的物理地址为20100H&#xff0c;当执行完指令PUSH…

数据结构初阶leetcodeOJ题(二)

目录 第一题 思路&#xff1a; 第二题 思路 第三题 描述 示例1 思路 总结&#xff1a;这种类似的题&#xff0c;都是用快慢指针&#xff0c;相差一定的距离然后输出慢指针。 第一题 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val…

2023全新付费进群系统源码 带定位完整版 附教程

这源码是我付费花钱买的分享给大家&#xff0c;功能完整。 搭建教程 Nginx1.2 PHP5.6-7.2均可 最好是7.2 第一步上传文件程序到网站根目录解压 第二步导入数据库&#xff08;58soho.cn.sql&#xff09; 第三步修改/config/database.php里面的数据库地址 第四步修改/conf…

【漏洞复现】泛微e-Weaver SQL注入

漏洞描述 泛微e-Weaver&#xff08;FANWEI e-Weaver&#xff09;是一款广泛应用于企业数字化转型领域的集成协同管理平台。作为中国知名的企业级软件解决方案提供商&#xff0c;泛微软件&#xff08;广州&#xff09;股份有限公司开发和推广了e-Weaver平台。 泛微e-Weaver旨在…

LeetCode(28)盛最多水的容器【双指针】【中等】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 盛最多水的容器 1.题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水…

Java中如何通过路径表达式找值:XPath和JsonPath以及SpEL详解及对比

大家好&#xff0c;我是G探险者。 我们编程时&#xff0c;在前后端数据交互和传输过程中&#xff0c;往往需要对报文中的某个字段或者某个标签的值进行解析读取&#xff0c;报文通常是以json或者xml作为数据交换格式&#xff0c;而json和xml这两种格式的报文结构都是具备一定的…

CI/CD -gitlab

目录 一、常用命令 二、部署 一、常用命令 官网&#xff1a;https://about.gitlab.com/install/ gitlab-ctl start # 启动所有 gitlab 组件 gitlab-ctl stop # 停止所有 gitlab 组件 gitlab-ctl restart # 重启所有 gitlab 组件 gitlab-ctl statu…

比Postman强在哪里

Postman的受众对象主要是广大开发人员&#xff0c;调测使用&#xff0c;它并不能完全满足专业测试人员需求&#xff0c;而自动化测试平台可以 1&#xff0c;Postman&#xff0c;Jmter是单机版软件&#xff0c;类似打游戏你和电脑PK&#xff0c;而很多时候是要联网和其他人团队作…

软件开发、网络空间安全、人工智能三个方向的就业和前景怎么样?哪个方向更值得学习?

软件开发、网络空间安全、人工智能这三个方向都是当前及未来的热门领域&#xff0c;每个领域都有各自的就业前景和价值&#xff0c;以下是对这三个方向的分析&#xff1a; 1、软件开发&#xff1a; 就业前景&#xff1a;随着信息化的加速&#xff0c;软件开发的需求日益增长。…

【PyQt小知识 - 3】: QComboBox下拉框内容的设置和更新、默认值的设置、值和下标的获取

QComboBox 内容的设置和更新 from PyQt5.QtWidgets import * import sysapp QApplication(sys.argv)mainwindow QMainWindow() mainwindow.resize(200, 200) # 设置下拉框 comboBox QComboBox(mainwindow) comboBox.addItems([上, 中, 下])button QPushButton(更新, main…

Django学习日志03

数据的增删改查&#xff08;insert update delete select&#xff09; 1. 用户列表的展示 # 把数据表中得用户数据都给查询出来展示在页面上 添加数据 id username password gender age action …

Web与DNS综合实验

目录 题目&#xff1a; 步骤一&#xff1a;准备工作 步骤二&#xff1a;在server端搭建简单网页 步骤三&#xff1a;node1端的DNS解析配置 步骤五&#xff1a;node2端进行测试。 题目&#xff1a; 1.打开3个主机&#xff0c;server、node1、node2 2.server为web主机建立网…

如何将 Docsify 项目部署到 CentOS 系统的 Nginx 中?

文章目录 1. 介绍2. 准备工作3. 将 Docsify 项目上传至服务器4. 在服务器上安装 Node.js5. 在服务器上运行 Docsify6. 配置 Nginx 反向代理7. 访问 Docsify 文档8. 拓展8.1 配置 HTTPS8.2 定制 Docsify 主题8.3 鉴权和访问控制 &#x1f389;如何将 Docsify 项目部署到 CentOS …

​软考-高级-系统架构设计师教程(清华第2版)【第20章 系统架构设计师论文写作要点(P717~728)-思维导图】​

软考-高级-系统架构设计师教程&#xff08;清华第2版&#xff09;【第20章 系统架构设计师论文写作要点&#xff08;P717~728&#xff09;-思维导图】 课本里章节里所有蓝色字体的思维导图

图片标注工具Labelme的安装及使用方法

参考&#xff1a;图像语义分割标注工具labelme制作自己的数据集用于mask-rcnn训练_ZealCV的博客-CSDN博客_语义分割标注工具 在做目标检测任务时&#xff0c;需要用到labelImg进行画框标注&#xff0c;在之前的文章中已经介绍过该工具的使用方法。然而如果是做语义分割的任务时…

Linux命令之查看文件和权限修改操作

目录 查看文件 1. cat --- 将文件中的内容打印在输出设备 2. more --- 分页显示文件内容 3.less ---查看文件内容 4. head -- 查看文件前n行内容 5.tail -- 查看指定文件的后n行内容或实时监测文件 6. wc -- 可计算文件的字节数、字数和列数 文件搜索 1.which --- 获取…

大数据可视化是什么?

大数据可视化是将海量数据通过视觉方式呈现出来&#xff0c;以便于人们理解和分析数据的过程。它可以帮人们发现数据之间的关系、趋势和模式&#xff0c;并制定更明智的决策。大数据可视化通常通过图形、图表、地图和仪表盘等视觉元素来呈现数据。这些元素具有直观、易理解的特…

Prompt 编程的设计技巧

大家好&#xff0c;我是木川 《Prompt 编程》即利用 GPT 模型的能力实现编程效果&#xff0c;《Prompt 编程》最早是由菠菜老师提出&#xff0c;本文基于 《Prompt 编程》的概念及自己的一些感想&#xff0c;总结了下《 Prompt 编程》的设计技巧 一、结构化 针对复杂的 Prompt&…