Minimum Distance Between Alphabets: Given a string S and two alphabets C1 and C2 present in S, find the minimum distance D between C1 and C2 in S. Input Format: The first line will contain S. The second line will contain C1 and C2 separated by a space. Output Format: The first line will contain D. Boundary Conditions: 2 <= Length of S <= 100 Example Input/Output
1: Input: spaceship c s Output: 1 #include <iostream>
using namespace std;
int main(int argc, char** argv)
{
string s;
cin>>s;
char a,b;
cin>>a;
cin>>b;
int m=s.length(),flag=0,d=0;
for(int i=0;i<s.length();i++)
{
if(s[i]==a||s[i]==b)
{
if(flag==1&&d!=0)
{
if(d<m)
m=d;
d=0;
}
else
flag=1;
}
if(flag==1)
d++;
}
cout<<m-1;
}
Given a string of length n and a non-negative integer k. Find k distant string of given string. Distance between two letters is difference between their positions in the alphabet. for example: - dist(c, e) = dist(e, c) = 2.
- dist(a, z) = dist(z, a) = 25.
By using this concept, the distance between two strings is the sum of distances of corresponding letters. For example : - dist(af, hf) = dist(a, h) + dist(f, f) = 7 + 0 = 7.
Given a string
and a distance k. Task is to find a string such that distance of the result string is k from given string. If k distant string is not possible, then print “No”. Note: There may be exist multiple solutions. We need to find one of them. Examples : Input : bear
k = 26
Output : zcar
Here, dist(bear, zcar) =
dist(b, z) + dist(e, c) +
+ dist(a, a) + dist(r, r)
= 24 + 2 + 0 + 0
= 26
Input : af
k = 7
Output : hf
Here, dist(af, hf) = dist(a, h) + dist(f, f)
= 7 + 0
= 7
Input : hey
k = 1000
Output : No
Explanation :
No such string exists. There is no solution if the given required distance is too big. Think what is the maximum possible distance for the given string. Or the more useful thing — how to construct the lost
string to maximize the distance? Treat each letter separately and replace it with the most distant letter. For example, we should replace ‘c’ with ‘z’, and we should replace ‘y’ with ‘a’. To be more precise, for first 13 letters of the alphabet the most distant letter is ‘z’, and for other letters it is ‘a’. The approach is simple, iterate over letters of the given string and greedily change them. A word “greedily” means when changing a letter, don’t care about the next letters.
Generally, there must be distant letters, because there may not be a solution otherwise. For each letter of the given string change it into the most distant letter, unless the total distance would be too big. As letters are changed, decrease the remaining required distance. So, for each letter of the given string consider only letters not exceeding the remaining distance, and among them choose the most distant one. CPP and JAVA Implementation: Implementation:
CPP#include <bits/stdc++.h>
using namespace std;
string findKDistantString(string str, int k)
{
int n = str.length();
for ( int i = 0; i < n; ++i) {
char best_letter = str[i];
int best_distance = 0;
for ( char maybe = 'a' ;
maybe <= 'z' ; ++maybe)
{
int distance = abs (maybe - str[i]);
if (distance <= k && distance >
best_distance)
{
best_distance = distance;
best_letter = maybe;
}
}
k -= best_distance;
str[i] = best_letter;
}
assert (k >= 0);
if (k > 0)
return "No" ;
else
return str;
}
int main()
{
string str = "bear" ;
int k = 26;
cout << findKDistantString(str, k) << endl;
str = "af" ;
k = 7;
cout << findKDistantString(str, k) << endl;
return 0;
}
Javaimport java.util.*;
import java.lang.*;
public class GfG {
public static String findKDistantString
(String str1, int k)
{
int n = str1.length();
char [] str = str1.toCharArray();
for ( int i = 0 ; i < n; ++i) {
char best_letter = str[i];
int
best_distance = 0 ;
for ( char maybe = 'a' ;
maybe <= 'z' ; ++maybe)
{
int distance =
Math.abs(maybe - str[i]);
if (distance <= k && distance
> best_distance)
{
best_distance = distance;
best_letter = maybe;
}
}
k -= best_distance;
str[i] = best_letter;
}
assert (k >= 0 );
if
(k > 0 )
return "No" ;
else
return ( new String(str));
}
public static void main(String argc[])
{
String str = "bear" ;
int k = 26 ;
System.out.println(findKDistantString(str, k));
str = "af" ;
k = 7 ;
System.out.println(findKDistantString(str, k));
}
}
Python3
MAX = 26
def function(st):
global MAX
l = len (st)
counter1, counter2 = [ 0 ] * MAX , [ 0 ] * MAX
for i in range (l / / 2 ):
counter1[ ord (st[i]) - ord ( 'a' )] + = 1
for
i in range (l / / 2 , l):
counter2[ ord (st[i]) - ord ( 'a' )] + = 1
for i in range ( MAX ):
if (counter2[i] ! = counter1[i]):
return True
return False
st = "abcasdsabcae"
if function(st): print ( "Yes, both halves differ by at least one character" )
else : print ( "No, both halves do not differ at all" )
C#using System;
class GfG {
public static String findKDistantString
( string str1, int k)
{
int n = str1.Length;
char []str = str1.ToCharArray();
for ( int i = 0; i < n; ++i) {
char best_letter = str[i];
int best_distance = 0;
for ( char maybe = 'a' ;
maybe <= 'z' ; ++maybe)
{
int distance =
Math.Abs(maybe - str[i]);
if (distance <= k && distance
> best_distance)
{
best_distance = distance;
best_letter = maybe;
}
}
k -= best_distance;
str[i] = best_letter;
}
if (k > 0)
return "No" ;
else
return ( new string (str));
}
public
static void Main()
{
string str = "bear" ;
int k = 26;
Console.WriteLine(
findKDistantString(str, k));
str = "af" ;
k = 7;
Console.Write(
findKDistantString(str, k));
}
}
Javascript<script>
function findKDistantString(str,k)
{
let n = str.length;
for (let i = 0; i < n; ++i) {
let best_letter = str[i];
let best_distance = 0;
for (let maybe = 97; maybe <= 122; ++maybe)
{
let distance = Math.abs(maybe - str.charCodeAt(i));
if (distance <= k && distance >
best_distance)
{
best_distance = distance;
best_letter = String.fromCharCode(maybe);
}
}
k -= best_distance;
str = str.replace(str[i],best_letter);
}
if (k == 0)
return str;
else
return "No" ;
}
let str = "bear" ;
let k = 26;
document.write(findKDistantString(str, k), "</br>" );
str = "af" ;
k = 7;
document.write(findKDistantString(str, k), "</br>" );
</script>
How do you find the distance between two letters in python?
You can just use the str. index(char, [beg, end]) method to retrieve the position of a character inside a string. The method allows you to add a beginning and end position that you can use to check for the different occurrences. Using multiple lines you could avoid calling the s.
What is the distance between two alphabets or letters?
Distance between two letters is difference between their positions in the alphabet. for example: dist(c, e) = dist(e, c) = 2. dist(a, z) = dist(z, a) = 25.
How do you find the minimum distance between code words?
A code's minimum distance is the minimum of d(u,v) over all distinct codewords u and v. If the minimum distance is at least 2t + 1, a nearest neighbor decoder will always decode correctly when there are t or fewer errors.
|