Shortest window that include all characters of another string
Here given code implementation process.
// Java program for
// Shortest window that include all characters of another string
public class ShortestWindow
{
void minLengthWindows(String sequence, String text)
{
// Get the length of given string
int n = sequence.length();
int m = text.length();
if (n == 0 || n < m)
{
return;
}
int start = 0;
int startIndex = -1;
int minLength = n + m;
int count = 0;
int[] sequenceCount = new int[256];
int[] textCount = new int[256];
// Set initial character frequency
for (int i = 0; i < 256; ++i)
{
sequenceCount[i] = 0;
textCount[i] = 0;
}
// Count frequency of given text
for (int i = 0; i < m; i++)
{
textCount[text.charAt(i)] += 1;
}
// Count frequency of given sequence and
// find minimum character resultant window.
for (int i = 0; i < n; ++i)
{
// Increase character frequency
sequenceCount[sequence.charAt(i)]++;
if (textCount[sequence.charAt(i)] != 0 &&
sequenceCount[sequence.charAt(i)] <=
textCount[sequence.charAt(i)])
{
count++;
}
if (count == m)
{
while (sequenceCount[sequence.charAt(start)] >
textCount[sequence.charAt(start)] ||
textCount[sequence.charAt(start)] == 0)
{
if (sequenceCount[sequence.charAt(start)] >
textCount[sequence.charAt(start)])
{
sequenceCount[sequence.charAt(start)]--;
}
start++;
}
if (minLength > (i - start + 1))
{
startIndex = start;
minLength = (i - start + 1);
}
}
}
// Display given strings
System.out.println("\n Given Text : " + text);
System.out.println(" Given Sequence : " + sequence);
System.out.print(" Result : ");
if (startIndex == -1)
{
System.out.println("\n None ");
}
else
{
for (int i = startIndex; i < startIndex + minLength; ++i)
{
System.out.print(sequence.charAt(i));
}
}
}
public static void main(String[] args)
{
ShortestWindow task = new ShortestWindow();
String sequence = "xyeeezayxipc";
String text = "xyz";
task.minLengthWindows(sequence, text);
}
}
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
// Include header file
#include <iostream>
#include <string>
using namespace std;
// C++ program for
// Shortest window that include all characters of another string
class ShortestWindow
{
public: void minLengthWindows(string sequence, string text)
{
// Get the length of given string
int n = sequence.length();
int m = text.length();
if (n == 0 || n < m)
{
return;
}
int start = 0;
int startIndex = -1;
int minLength = n + m;
int count = 0;
int sequenceCount[256];
int textCount[256];
// Set initial character frequency
for (int i = 0; i < 256; ++i)
{
sequenceCount[i] = 0;
textCount[i] = 0;
}
// Count frequency of given text
for (int i = 0; i < m; i++)
{
textCount[text[i]] += 1;
}
// Count frequency of given sequence and
// find minimum character resultant window.
for (int i = 0; i < n; ++i)
{
// Increase character frequency
sequenceCount[sequence[i]]++;
if (textCount[sequence[i]] != 0 &&
sequenceCount[sequence[i]] <= textCount[sequence[i]])
{
count++;
}
if (count == m)
{
while (sequenceCount[sequence[start]] >
textCount[sequence[start]] ||
textCount[sequence[start]] == 0)
{
if (sequenceCount[sequence[start]] >
textCount[sequence[start]])
{
sequenceCount[sequence[start]]--;
}
start++;
}
if (minLength > (i - start + 1))
{
startIndex = start;
minLength = (i - start + 1);
}
}
}
// Display given strings
cout << "\n Given Text : " << text << endl;
cout << " Given Sequence : " << sequence << endl;
cout << " Result : ";
if (startIndex == -1)
{
cout << "\n None " << endl;
}
else
{
for (int i = startIndex; i < startIndex + minLength; ++i)
{
cout << sequence[i];
}
}
}
};
int main()
{
ShortestWindow *task = new ShortestWindow();
string sequence = "xyeeezayxipc";
string text = "xyz";
task->minLengthWindows(sequence, text);
return 0;
}
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
// Include namespace system
using System;
// Csharp program for
// Shortest window that include all characters of another string
public class ShortestWindow
{
void minLengthWindows(String sequence, String text)
{
// Get the length of given string
int n = sequence.Length;
int m = text.Length;
if (n == 0 || n < m)
{
return;
}
int start = 0;
int startIndex = -1;
int minLength = n + m;
int count = 0;
int[] sequenceCount = new int[256];
int[] textCount = new int[256];
// Set initial character frequency
for (int i = 0; i < 256; ++i)
{
sequenceCount[i] = 0;
textCount[i] = 0;
}
// Count frequency of given text
for (int i = 0; i < m; i++)
{
textCount[text[i]] += 1;
}
// Count frequency of given sequence and
// find minimum character resultant window.
for (int i = 0; i < n; ++i)
{
// Increase character frequency
sequenceCount[sequence[i]]++;
if (textCount[sequence[i]] != 0 &&
sequenceCount[sequence[i]] <= textCount[sequence[i]])
{
count++;
}
if (count == m)
{
while (sequenceCount[sequence[start]] >
textCount[sequence[start]] ||
textCount[sequence[start]] == 0)
{
if (sequenceCount[sequence[start]] >
textCount[sequence[start]])
{
sequenceCount[sequence[start]]--;
}
start++;
}
if (minLength > (i - start + 1))
{
startIndex = start;
minLength = (i - start + 1);
}
}
}
// Display given strings
Console.WriteLine("\n Given Text : " + text);
Console.WriteLine(" Given Sequence : " + sequence);
Console.Write(" Result : ");
if (startIndex == -1)
{
Console.WriteLine("\n None ");
}
else
{
for (int i = startIndex; i < startIndex + minLength; ++i)
{
Console.Write(sequence[i]);
}
}
}
public static void Main(String[] args)
{
ShortestWindow task = new ShortestWindow();
String sequence = "xyeeezayxipc";
String text = "xyz";
task.minLengthWindows(sequence, text);
}
}
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
package main
import "fmt"
// Go program for
// Shortest window that include all characters of another string
func minLengthWindows(sequence, text string) {
// Get the length of given string
var n int = len(sequence)
var m int = len(text)
if n == 0 || n < m {
return
}
var start int = 0
var startIndex int = -1
var minLength int = n + m
var count int = 0
// Set initial character frequency
var sequenceCount = make([] int, 256)
var textCount = make([] int, 256)
// Count frequency of given text
for i := 0 ; i < m ; i++ {
textCount[text[i]] += 1
}
// Count frequency of given sequence and
// find minimum character resultant window.
for i := 0 ; i < n ; i++ {
// Increase character frequency
sequenceCount[sequence[i]]++
if textCount[sequence[i]] != 0 && sequenceCount[sequence[i]] <= textCount[sequence[i]] {
count++
}
if count == m {
for (sequenceCount[sequence[start]] > textCount[sequence[start]] || textCount[sequence[start]] == 0) {
if sequenceCount[sequence[start]] > textCount[sequence[start]] {
sequenceCount[sequence[start]]--
}
start++
}
if minLength > (i - start + 1) {
startIndex = start
minLength = (i - start + 1)
}
}
}
// Display given strings
fmt.Println("\n Given Text : ", text)
fmt.Println(" Given Sequence : ", sequence)
fmt.Print(" Result : ")
if startIndex == -1 {
fmt.Println("\n None ")
} else {
for i := startIndex ; i < startIndex + minLength ; i++ {
fmt.Print(string(sequence[i]))
}
}
}
func main() {
var sequence string = "xyeeezayxipc"
var text string = "xyz"
minLengthWindows(sequence, text)
}
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
<?php
// Php program for
// Shortest window that include all characters of another string
class ShortestWindow
{
function minLengthWindows($sequence, $text)
{
// Get the length of given string
$n = strlen($sequence);
$m = strlen($text);
if ($n == 0 || $n < $m)
{
return;
}
$start = 0;
$startIndex = -1;
$minLength = $n + $m;
$count = 0;
// Set initial character frequency
$sequenceCount = array_fill(0, 256, 0);
$textCount = array_fill(0, 256, 0);
// Count frequency of given text
for ($i = 0; $i < $m; $i++)
{
$textCount[ord($text[$i])] += 1;
}
// Count frequency of given sequence and
// find minimum character resultant window.
for ($i = 0; $i < $n; ++$i)
{
// Increase character frequency
$sequenceCount[ord($sequence[$i])]++;
if ($textCount[ord($sequence[$i])] != 0 &&
$sequenceCount[ord($sequence[$i])] <=
$textCount[ord($sequence[$i])])
{
$count++;
}
if ($count == $m)
{
while ($sequenceCount[ord($sequence[$start])] >
$textCount[ord($sequence[$start])] ||
$textCount[ord($sequence[$start])] == 0)
{
if ($sequenceCount[ord($sequence[$start])] >
$textCount[ord($sequence[$start])])
{
$sequenceCount[ord($sequence[$start])]--;
}
$start++;
}
if ($minLength > ($i - $start + 1))
{
$startIndex = $start;
$minLength = ($i - $start + 1);
}
}
}
// Display given strings
echo("\n Given Text : ".$text."\n");
echo(" Given Sequence : ".$sequence."\n");
echo(" Result : ");
if ($startIndex == -1)
{
echo("\n None "."\n");
}
else
{
for ($i = $startIndex; $i < $startIndex + $minLength; ++$i)
{
echo($sequence[$i]);
}
}
}
}
function main()
{
$task = new ShortestWindow();
$sequence = "xyeeezayxipc";
$text = "xyz";
$task->minLengthWindows($sequence, $text);
}
main();
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
// Node JS program for
// Shortest window that include all characters of another string
class ShortestWindow
{
minLengthWindows(sequence, text)
{
// Get the length of given string
var n = sequence.length;
var m = text.length;
if (n == 0 || n < m)
{
return;
}
var start = 0;
var startIndex = -1;
var minLength = n + m;
var count = 0;
// Set initial character frequency
var sequenceCount = Array(256).fill(0);
var textCount = Array(256).fill(0);
// Count frequency of given text
for (var i = 0; i < m; i++)
{
textCount[text.charAt(i).charCodeAt(0)] += 1;
}
// Count frequency of given sequence and
// find minimum character resultant window.
for (var i = 0; i < n; ++i)
{
// Increase character frequency
sequenceCount[sequence.charAt(i).charCodeAt(0)]++;
if (textCount[sequence.charAt(i).charCodeAt(0)] != 0 &&
sequenceCount[sequence.charAt(i).charCodeAt(0)] <=
textCount[sequence.charAt(i).charCodeAt(0)])
{
count++;
}
if (count == m)
{
while (sequenceCount[sequence.charAt(start).charCodeAt(0)] >
textCount[sequence.charAt(start).charCodeAt(0)] ||
textCount[sequence.charAt(start).charCodeAt(0)] == 0)
{
if (sequenceCount[sequence.charAt(start).charCodeAt(0)] >
textCount[sequence.charAt(start).charCodeAt(0)])
{
sequenceCount[sequence.charAt(start).charCodeAt(0)]--;
}
start++;
}
if (minLength > (i - start + 1))
{
startIndex = start;
minLength = (i - start + 1);
}
}
}
// Display given strings
console.log("\n Given Text : " + text);
console.log(" Given Sequence : " + sequence);
process.stdout.write(" Result : ");
if (startIndex == -1)
{
console.log("\n None ");
}
else
{
for (var i = startIndex; i < startIndex + minLength; ++i)
{
process.stdout.write(sequence.charAt(i));
}
}
}
}
function main()
{
var task = new ShortestWindow();
var sequence = "xyeeezayxipc";
var text = "xyz";
task.minLengthWindows(sequence, text);
}
main();
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
# Python 3 program for
# Shortest window that include all characters of another string
class ShortestWindow :
def minLengthWindows(self, sequence, text) :
# Get the length of given string
n = len(sequence)
m = len(text)
if (n == 0 or n < m) :
return
start = 0
startIndex = -1
minLength = n + m
count = 0
# Set initial character frequency
sequenceCount = [0] * (256)
textCount = [0] * (256)
i = 0
# Count frequency of given text
while (i < m) :
textCount[ord(text[i])] += 1
i += 1
i = 0
# Count frequency of given sequence and
# find minimum character resultant window.
while (i < n) :
# Increase character frequency
sequenceCount[ord(sequence[i])] += 1
if (textCount[ord(sequence[i])] != 0 and
sequenceCount[ord(sequence[i])] <=
textCount[ord(sequence[i])]) :
count += 1
if (count == m) :
while (sequenceCount[ord(sequence[start])] >
textCount[ord(sequence[start])] or
textCount[ord(sequence[start])] == 0) :
if (sequenceCount[ord(sequence[start])] >
textCount[ord(sequence[start])]) :
sequenceCount[ord(sequence[start])] -= 1
start += 1
if (minLength > (i - start + 1)) :
startIndex = start
minLength = (i - start + 1)
i += 1
# Display given strings
print("\n Given Text : ", text)
print(" Given Sequence : ", sequence)
print(" Result : ", end = "")
if (startIndex == -1) :
print("\n None ")
else :
i = startIndex
while (i < startIndex + minLength) :
print(sequence[i], end = "")
i += 1
def main() :
task = ShortestWindow()
sequence = "xyeeezayxipc"
text = "xyz"
task.minLengthWindows(sequence, text)
if __name__ == "__main__": main()
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
# Ruby program for
# Shortest window that include all characters of another string
class ShortestWindow
def minLengthWindows(sequence, text)
# Get the length of given string
n = sequence.length
m = text.length
if (n == 0 || n < m)
return
end
start = 0
startIndex = -1
minLength = n + m
count = 0
# Set initial character frequency
sequenceCount = Array.new(256) {0}
textCount = Array.new(256) {0}
i = 0
# Count frequency of given text
while (i < m)
textCount[text[i].ord] += 1
i += 1
end
i = 0
# Count frequency of given sequence and
# find minimum character resultant window.
while (i < n)
# Increase character frequency
sequenceCount[sequence[i].ord] += 1
if (textCount[sequence[i].ord] != 0 &&
sequenceCount[sequence[i].ord] <= textCount[sequence[i].ord])
count += 1
end
if (count == m)
while (sequenceCount[sequence[start].ord] >
textCount[sequence[start].ord] ||
textCount[sequence[start].ord] == 0)
if (sequenceCount[sequence[start].ord] >
textCount[sequence[start].ord])
sequenceCount[sequence[start].ord] -= 1
end
start += 1
end
if (minLength > (i - start + 1))
startIndex = start
minLength = (i - start + 1)
end
end
i += 1
end
# Display given strings
print("\n Given Text : ", text, "\n")
print(" Given Sequence : ", sequence, "\n")
print(" Result : ")
if (startIndex == -1)
print("\n None ", "\n")
else
i = startIndex
while (i < startIndex + minLength)
print(sequence[i])
i += 1
end
end
end
end
def main()
task = ShortestWindow.new()
sequence = "xyeeezayxipc"
text = "xyz"
task.minLengthWindows(sequence, text)
end
main()
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
import scala.collection.mutable._;
// Scala program for
// Shortest window that include all characters of another string
class ShortestWindow()
{
def minLengthWindows(sequence: String, text: String): Unit = {
// Get the length of given string
var n: Int = sequence.length();
var m: Int = text.length();
if (n == 0 || n < m)
{
return;
}
var start: Int = 0;
var startIndex: Int = -1;
var minLength: Int = n + m;
var count: Int = 0;
// Set initial character frequency
var sequenceCount: Array[Int] = Array.fill[Int](256)(0);
var textCount: Array[Int] = Array.fill[Int](256)(0);
var i: Int = 0;
// Count frequency of given text
while (i < m)
{
textCount(text.charAt(i)) += 1;
i += 1;
}
i = 0;
// Count frequency of given sequence and
// find minimum character resultant window.
while (i < n)
{
// Increase character frequency
sequenceCount(sequence.charAt(i)) += 1;
if (textCount(sequence.charAt(i)) != 0 &&
sequenceCount(sequence.charAt(i)) <=
textCount(sequence.charAt(i)))
{
count += 1;
}
if (count == m)
{
while (sequenceCount(sequence.charAt(start)) >
textCount(sequence.charAt(start)) ||
textCount(sequence.charAt(start)) == 0)
{
if (sequenceCount(sequence.charAt(start)) >
textCount(sequence.charAt(start)))
{
sequenceCount(sequence.charAt(start)) -= 1;
}
start += 1;
}
if (minLength > (i - start + 1))
{
startIndex = start;
minLength = (i - start + 1);
}
}
i += 1;
}
// Display given strings
println("\n Given Text : " + text);
println(" Given Sequence : " + sequence);
print(" Result : ");
if (startIndex == -1)
{
println("\n None ");
}
else
{
i = startIndex;
while (i < startIndex + minLength)
{
print(sequence.charAt(i));
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: ShortestWindow = new ShortestWindow();
var sequence: String = "xyeeezayxipc";
var text: String = "xyz";
task.minLengthWindows(sequence, text);
}
}
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
import Foundation;
// Swift 4 program for
// Shortest window that include all characters of another string
class ShortestWindow
{
func minLengthWindows(_ s: String, _ t: String)
{
let sequence = Array(s);
let text = Array(t);
// Get the length of given string
let n: Int = sequence.count;
let m: Int = text.count;
if (n == 0 || n < m)
{
return;
}
var start: Int = 0;
var startIndex: Int = -1;
var minLength: Int = n + m;
var count: Int = 0;
// Set initial character frequency
var sequenceCount: [Int] = Array(repeating: 0, count: 256);
var textCount: [Int] = Array(repeating: 0, count: 256);
var i: Int = 0;
// Count frequency of given text
while (i < m)
{
textCount[Int(UnicodeScalar(String(text[i]))!.value)] += 1;
i += 1;
}
i = 0;
// Count frequency of given sequence and
// find minimum character resultant window.
while (i < n)
{
// Increase character frequency
sequenceCount[Int(UnicodeScalar(String(sequence[i]))!.value)] += 1;
if (textCount[Int(UnicodeScalar(String(sequence[i]))!.value)] != 0 &&
sequenceCount[Int(UnicodeScalar(String(sequence[i]))!.value)] <=
textCount[Int(UnicodeScalar(String(sequence[i]))!.value)])
{
count += 1;
}
if (count == m)
{
while (sequenceCount[Int(UnicodeScalar(String(sequence[start]))!.value)] >
textCount[Int(UnicodeScalar(String(sequence[start]))!.value)] ||
textCount[Int(UnicodeScalar(String(sequence[start]))!.value)] == 0)
{
if (sequenceCount[Int(UnicodeScalar(String(sequence[start]))!.value)] >
textCount[Int(UnicodeScalar(String(sequence[start]))!.value)])
{
sequenceCount[Int(UnicodeScalar(String(sequence[start]))!.value)] -= 1;
}
start += 1;
}
if (minLength > (i - start + 1))
{
startIndex = start;
minLength = (i - start + 1);
}
}
i += 1;
}
// Display given strings
print("\n Given Text : ", t);
print(" Given Sequence : ", s);
print(" Result : ", terminator: "");
if (startIndex == -1)
{
print("\n None ");
}
else
{
i = startIndex;
while (i < startIndex + minLength)
{
print(sequence[i], terminator: "");
i += 1;
}
}
}
}
func main()
{
let task: ShortestWindow = ShortestWindow();
let sequence: String = "xyeeezayxipc";
let text: String = "xyz";
task.minLengthWindows(sequence, text);
}
main();
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
// Kotlin program for
// Shortest window that include all characters of another string
class ShortestWindow
{
fun minLengthWindows(sequence: String, text: String): Unit
{
// Get the length of given string
val n: Int = sequence.length;
val m: Int = text.length;
if (n == 0 || n < m)
{
return;
}
var start: Int = 0;
var startIndex: Int = -1;
var minLength: Int = n + m;
var count: Int = 0;
// Set initial character frequency
val sequenceCount: Array < Int > = Array(256)
{
0
};
val textCount: Array < Int > = Array(256)
{
0
};
var i: Int = 0;
// Count frequency of given text
while (i < m)
{
textCount[text.get(i).toInt()] += 1;
i += 1;
}
i = 0;
// Count frequency of given sequence and
// find minimum character resultant window.
while (i < n)
{
// Increase character frequency
sequenceCount[sequence.get(i).toInt()] += 1;
if (textCount[sequence.get(i).toInt()] != 0 &&
sequenceCount[sequence.get(i).toInt()] <=
textCount[sequence.get(i).toInt()])
{
count += 1;
}
if (count == m)
{
while (sequenceCount[sequence.get(start).toInt()] >
textCount[sequence.get(start).toInt()] ||
textCount[sequence.get(start).toInt()] == 0)
{
if (sequenceCount[sequence.get(start).toInt()] >
textCount[sequence.get(start).toInt()])
{
sequenceCount[sequence.get(start).toInt()] -= 1;
}
start += 1;
}
if (minLength > (i - start + 1))
{
startIndex = start;
minLength = (i - start + 1);
}
}
i += 1;
}
// Display given strings
println("\n Given Text : " + text);
println(" Given Sequence : " + sequence);
print(" Result : ");
if (startIndex == -1)
{
println("\n None ");
}
else
{
i = startIndex;
while (i < startIndex + minLength)
{
print(sequence.get(i));
i += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
val task: ShortestWindow = ShortestWindow();
val sequence: String = "xyeeezayxipc";
val text: String = "xyz";
task.minLengthWindows(sequence, text);
}
Output
Given Text : xyz
Given Sequence : xyeeezayxipc
Result : zayx
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment